2014
02-10

f(n)

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.

There are several test case. For each test case:One integer n(3<=n<=1000000). The end of the in put file is EOF.

There are several test case. For each test case:One integer n(3<=n<=1000000). The end of the in put file is EOF.

3
26983

3
37556486

#include<iostream>
#include<cstdlib>
#include<stdio.h>
#define ll long long
#define M 1000001
using namespace std;
ll a[M];
int prime[79000],cnt;
bool f[M];
int fac(int n)
{
for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++){
if(n%prime[i]==0){
n/=prime[i];
while(n%prime[i]==0) n/=prime[i];
if(n==1) return prime[i];
return 0;
}
}
return 0;
}
void init()
{
int i,j,k;
cnt=0;
for(i=2;i<M;i++){
if(f[i]==0) prime[cnt++]=i;
for(j=0;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main()
{
int i,k,n;
init();
while(scanf("%d",&n)!=EOF){
ll ans=0;
for(i=3;i<=n;i++){
if(f[i]==0) ans+=i;
else{
k=fac(i);
if(k) ans+=k;
else ans+=1;
}
}
printf("%I64d\n",ans);
}
return 0;
}

1. 說得好！的確是這樣！！！除非外星人有一個全面性的與地球所有人接觸，不然現階段的社會組織架構，就是圍繞在金錢上面。請不要脫離現實！！