This time I need you to calculate the f(n) . (3<=n<=1000000)
f(n)= Gcd(3) Gcd(4) … Gcd(i) … Gcd(n). Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1]) C[n][k] means the number of way to choose k things from n some things. gcd(a,b) means the greatest common divisor of a and b. Input There are several test case. For each test case:One integer n(3<=n<=1000000). The end of the in put file is EOF. Output For each test case: The output consists of one line with one integer f(n). Sample Input 3 26983 Sample Output 3 37556486 题目就是这么短小精悍，这题我实在不知道怎么写，然后也不会数论的推理，我就打了表，发现跟质数的关系很大，就顺着推了一下， 就过了。
代码语言：javascript复制#include <iostream>
#include<cstdio>
#define ll long long
#define maxn 1000000
using namespace std;
int zs[maxn], t = 0, n;
ll f[maxn 5];
bool v[maxn 5];
int main()
{
for (int i = 2; i <= maxn; i )
{
if (!v[i]) f[i] = zs[ t] = i;
for (int j = 1,u = zs[j] * i; j <= t && u<= maxn; j )
{
v[u] = 1;
if (!(i % zs[j]))
{
f[u] = f[i];
break;
}
f[u] = 1;
u = zs[j 1] * i;
}
}
for (int i = 4; i <= maxn; i )
f[i] = f[i - 1];
while (scanf("%d", &n)!=EOF)
printf("%lldn", f[n]);
return 0;
}
