首页 > 代码库 > 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 最大公约数之和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。