hdoj f(n)2582(GCDは時計を打って&法則を探します)良い問題を探します

f(n)
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 378    Accepted Submission(s): 230
Problem Description
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
   
   
   
   

 
表を打ってGCDの法則を探すと、GCD(n)は、nが1つの質量因子しかない場合、GCD(n)は1ではなく、このときGCDはnのこの唯一の質量因子に等しいことがわかります.

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll __int64
#define N 1000010
using namespace std;
ll p[N];
bool flag[N];
ll sum[N];
void init()
{
	__int64 i,j,num=0;
	for(i=2;i<=N;i++)
	{
		if(!flag[i])
		{
			p[num++]=i;
			for(j=i*i;j<=N;j+=i)
				flag[j]=true;
		}
	}
}
ll solve(ll n)
{
	ll i,k,ans=0;
	for(i=0;p[i]*p[i]<=n;i++)
	{
		if(n%p[i]==0)
		{
			n/=p[i];
			while(n%p[i]==0)
				n/=p[i];
			k=p[i];
			ans++;
		}
		if(ans>=2)
			return 1;
	}
	if(n>1)
	{
		ans++;
		k=n;
	}
	if(ans>=2)
		return 1;
	else
		return k;
}
int main()
{
	ll n,i;
	init();
	for(i=3;i<=N;i++)
	{
		if(flag[i])
			sum[i]=sum[i-1]+solve(i);
		else
			sum[i]=sum[i-1]+i;
	}
	while(scanf("%d",&n)!=EOF)
		printf("%I64d
",sum[n]);
	return 0;
}