题目链接：传送门
感谢此大佬的博客：https://blog.csdn.net/codeswarrior/article/details/81263050 写的非常好！
题意：
给出公式Gcd(n)=gcd(C(n,1),C(n,2),……,C(n,n-1)
其中C(n,1)代表组合C，n选1，等于n！/1！/(n-1)!
让求f(n)=Gcd(3) Gcd(4) … Gcd(i) … Gcd(n)
输入N，求f(n)
分析：
最暴力的做法，就是写一个组合计算函数F(c)，依次把1到100W的gcd算出来.......
暴力终究是暴力，不能解决一切，参考了别人的博客，仔细推理了一下，还真成立
对于G=gcd(C(n,1),C(n,2)，C(n,3)...C(n,n-1) )来说
有且仅有以下三种情况：
(1) 如果n为素数，G=nG=n
(2) 如果n有两个或两个以上的素因子，G=1G=1
(3) 如果n只有一个素因子pp，G=p
证明过程见上面博客。
我们先把1到100W的素数筛选出来，放入prime数组，也顺带放入isprime数组可以方便后续o(1)判断是否素数
有几点需要注意的地方：
1.输入N>=3，不需要考虑小于3的数。
2.判断素因子个数的时候，没有从i=2开始到sqrt(x)，而是从prime素数堆中遍历，大大的省时。这点我刚开始没想到
3.if (sum == 1 && x == 1)代表素因子唯一
(sum == 1 && x > 1)代表素因子不唯一
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
bool isprime[1000010];
int prime[100000], len;
long long fx[1000001];
int dd(int x) {
int sum = 0;
int cnt = -1;
for (int i = 0; i < len && prime[i] * prime[i] <= x; i ) {
if (x % prime[i] == 0) {
cnt = prime[i];
sum ;
if (sum > 1) return 1;
while (x % prime[i] == 0) {
x /= prime[i];
}
}
}
if (sum == 1 && x == 1) return cnt;
if (sum == 1 && x > 1) return 1;
return 1;
}
void init() {
memset(isprime, true, sizeof(isprime));
len = 0;
for (int i = 2; i < 1000001; i ) {
if (isprime[i]) {
prime[len ] = i;
for (int j = i i; j <= 1000001; j = i) {
isprime[j] = false;
}
}
}
fx[2] = 0;
for (int i = 3; i <= 1000000; i ) {
if (isprime[i]) fx[i] = fx[i - 1] i;
else fx[i] = fx[i - 1] dd(i);
}
}
int main()
{
init();
int n;
while (~scanf_s("%d", &n)) {
printf("%lldn", fx[n]);
}
return 0;
}
