前天的晚上打这道题，和同学一起想出了思路，开心。
题意描述
给你一个数 \(N\)，问你存不存在一个数列 \(A_1,A_2,\ldots,A_n(2 \le n)\) ，使得 \(\sum_{i=1}^n A_i=N\) 并且 \(\operatorname{lcm}(A_1,A_2,\ldots,A_n)=N\)。
具体思路
首先显然，一个质数 \(N\) 的因数只有 \(1\) 和 \(N\)。
若选 \(N\)，那么个数不符合要求，
若选 \(1\) 和 \(N\)，那么和比 \(N\) 大，不符合要求。
因此质数肯定是不符合要求的。
考虑不是质数的情况。
我们从样例出发， \(6=2 \times 3\)，因此我们令 \(A_1=2,A_2=3\)。
但是我们发现和并不符合要求，而同时发现给数列中添加 \(1\) 并不会影响最后的最小公倍数。
因此我们令 \(A_3=1\) 即可。
想到这里你好像懂了什么，继续往下看。
样例中还有一个 \(4\)，它是不符合要求的，为什么？
由于我们可以通过补 \(1\) 的方式来保证和为 \(N\)，因此可以不用考虑和。
我们对 \(4\) 进行质因数分解，发现它只有 \(2\) 这一个质因子。
说明我们如果把它和 \(6\) 一样分成两个数相乘，由于它只有 \(2\) 这一个质因子，那么这两个数一定同时可以被 \(2\) 整除。
设这两个数分别为 \(a,b\)，其中 \(a \times b=4\)
那么 \(\operatorname{lcm}(a,b)=\frac{a \times b}{\gcd(a,b)}=\frac{a \times b}{2}=\frac{4}{2}=2\)。
我们发现最后答案不是 \(4\)。
一般的 \(N=p^c\)，有 \(\operatorname{lcm}(a,b)=\frac{a \times b}{\gcd(a,b)}=\frac{a \times b}{p}=\frac{N}{p}\)。
于是我们得出结论：
-
若 \(N\) 为质数，没有符合条件的数列。
-
若 \(N\) 不为质数且只有一个质因子，没有符合条件的数列。
-
若 \(N\) 不为质数且质因子个数 \(>1\)，有符合条件的数列。
Code
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
int cnt=0;
for(int i=2;i*i<=n;i++){
if(n%i==0){
cnt++;
while(n%i==0)n/=i;
}
}
if(n>1)cnt++;
if(cnt>1)puts("Yes");
else puts("No");
}
return 0;
}