首页 > ACM题库 > HDU-杭电 > hdu 2582 f(n)-最小生成树-[解题报告]C++
2014
02-10

hdu 2582 f(n)-最小生成树-[解题报告]C++

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

打表找规律:

 

当n为质数是,GCD(n)=n;

当n为质数k的q次方时,GCD(n)=k;

其他情况,GCD(n)=1.

代码如下:

 

#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;
 }

 

 

 

解题转自:http://www.cnblogs.com/xin-hua/p/3273497.html