HDU 2582 f(n) 素因子-白红宇

HDU 2582 f(n) 素因子

阅读量：3903 次

发布时间：2019-05-23

本文共 1538 字，大约阅读时间需要 5 分钟。

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

26983

Sample Output

37556486

代码及注释如下：

/*Gcd(3)=3;Gcd(4)=2;Gcd(5)=5;Gcd(6)=1;Gcd(7)=7;Gcd(8)=2;Gcd(9)=3;Gcd(10)=1;这道题的规律如下：1.如果为x素数，则Gcd(x)=x;2.如果素因子只有一个则Gcd(x)=素因子3.如果有多个素因子，则Gcd(x)=1;*/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=1000005;int n;int isnot[maxn];vector
         
           pri;long long int sum[maxn];void init(){ memset (isnot,0,sizeof(isnot)); memset (sum,0,sizeof(sum));}void Judge (){ for (int i=2;i<=maxn-5;i++) { if(!isnot[i]) { pri.push_back(i); for (int j=i*2;j<=maxn-5;j+=i) { isnot[j]=1; } } }}int Pnum (int x){ int num=0,p; for (int i=0;pri[i]*pri[i]<=x;i++) { if(x%pri[i]==0) { num++; if(num>1) return 1; p=pri[i]; while (x%pri[i]==0) { x/=pri[i]; } } } if(x!=1) { num++; x=n; } if(num>1) return 1; else return p;}int main(){ init(); Judge(); sum[3]=3; for (int i=4;i<=maxn-5;i++) { if(!isnot[i]) sum[i]=sum[i-1]+i; else sum[i]=sum[i-1]+Pnum(i); } while (scanf("%d",&n)!=EOF) { printf("%lld\n",sum[n]); } return 0;}