首页 > 代码库 > 1040 最大公约数之和

1040 最大公约数之和

1040 最大公约数之和
题目来源: rihkddd
基准时间限制:1 秒 空间限制:131072 KB 分值: 80
给出一个n,求1-n这n个数,同n的最大公约数的和。比如:n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6,加在一起 = 15
 
Input
1个数N(N <= 10^9)
Output
公约数之和
Input示例
6
Output示例
15
思路:欧拉函数;
找n的约数,k为n的一个约数,设s,n的最大公约数为k,那么我们可以知道gcd(s/k,n/k)=1,那么对应k对答案的贡献就是phi(n/k)*k;
 1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<stdlib.h> 5 #include<queue> 6 #include<string.h> 7 #include<math.h> 8 using namespace std; 9 typedef long long LL;10 bool prime[100005];11 int ans[100000];12 LL phi(LL n,int cn);13 int main(void)14 {15         int i,j;16         int cn = 0;17         for(i = 2; i  <= 1005; i++)18         {19                 if(!prime[i])20                 {21                         for(j = i; (i*j) <= 100005; j++)22                         {23                                 prime[i*j] = true;24                         }25                 }26         }27         for(i = 2; i <= 100005; i++)28         {29                 if(!prime[i])30                         ans[cn++] = i;31         }32         LL n;33         scanf("%lld",&n);34         LL sum = 0;35         for(i = 1; i <= sqrt(1.0*n); i++)36         {37                 if(n%i==0)38                 {39                         LL ak = n/i;40                         if(ak==i)41                         {42                                 sum += phi(n/i,cn)*(LL)i;43                         }44                         else45                         {46                                 sum += phi(n/i,cn)*(LL)i+phi(n/ak,cn)*(LL)ak;47                         }48                 }49         }50         printf("%lld\n",sum);51         return 0;52 }53 LL phi(LL n,int cn)54 {55         LL ap = sqrt(1.0*n);56         int i,j;57         LL t = n;58         int f = 0;59         int flag = 0;60         while(t>1)61         {62                 while(t%ans[f]==0)63                 {64                         if(flag == 0)65                         {66                                 flag = 1;67                                 n/=ans[f];68                                 n*=(ans[f]-1);69                         }70                         t /= ans[f];71                 }72                 f++;flag = 0;73                 if(ans[f]*ans[f]>t)74                         break;75         }76         if(t>1)77         {78                 n/=t;79                 n*=(t-1);80         }81         return n;82 }

 

 

1040 最大公约数之和