http://acm.hdu.edu.cn/showproblem.php?pid=2582
f(n)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 616 Accepted Submission(s): 373
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
Source
ECJTU 2009 Spring Contest
题意：f(n)=Gcd(3)+Gcd(4)+...+Gcd(n)，Gcd(n)为组合数C(n,i)的gcd，1<=i<=n-1。
题解：写出几项结合组合数的公式可以发现。当k的因子中不止一个素因子时gcd(k)=1，只有一个素因子时gcd(k)=该素因子。然后前几天学的素数筛法就很巧妙的筛出了这两种k。
代码：
#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;
const int N = 1000000 + 5;
const int mod = 1000000000 + 7;
int n,prime[N];
LL ans;
int main(){
mem(prime,0);
for(int i=2;i<N;i++){
if(!prime[i]){//本身是素数
prime[i]=i;
for(int j=prime[i]+prime[i];j<N;j+=prime[i]){//素数的倍数
if(!prime[j]){
prime[j]=i;
}
else{//不止一个素因子时
prime[j]=1;
}
}
}
}
while(~scanf("%d",&n)){
ans=0;
for(int i=3;i<=n;i++){
ans+=prime[i];
}
printf("%lld\n",ans);
}
return 0;
}
