首页 > 代码库 > NYOJ-569最大公约数之和
NYOJ-569最大公约数之和
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=569
此题目可以用筛选法的思想来做，但是用到一个欧拉函数
gcd（1，12）=1，gcd（5，12）=1，gcd（7，12）=1，gcd（11，12）=1，
gcd（2，12）=2，gcd（10，12）=2，
gcd（3，12）=3，gcd（9，12）=3，
gcd（4，12）=4，gcd（8，12）=4，
gcd（6，12）=6，
gcd（12，12）=12，
gcd（1，12）+gcd（2，12）+gcd（3，12）+gcd（4，12）+gcd（5，12）+gcd（6，12）+
gcd（7，12）+gcd（8，12）+gcd（9，12）+gcd（10，12）+gcd（11，12）+gcd（12，12）
=4*1+2*2+2*3+2*4+1*6+1*12=40
φ（12）*1+φ（6）*2+φ（4）*3+φ（3）*4+φ（2）*6+φ（1）*12
=4*1+2*2+2*3+2*4+1*6+1*12
=40
其中φ(x)是欧拉函数，意思就是从1-x中所有与x互质的个数
以上是推倒过程， 这个题目主要就是球欧拉函数和推倒出这个表达式
代码如下：
1 #include<iostream> 2 #include <cstdio> 3 using namespace std; 4 5 int Eular(int n) 6 { 7 int ans = n; 8 for(int i = 2; i * i <= n; i++) 9 {10 if(n % i == 0) //如果i 和 n不互质， 则i的倍数和n也不互质11 {12 ans -= ans / i; //去除掉i的倍数13 while(n % i == 0) //去掉n中所有i的因子14 n /= i;15 if(n == 1) // n = 1时， 所以因子排除完毕16 break;17 }18 }19 if(n != 1) //如果n为质数20 ans -= ans / n;21 return ans;22 }23 int main()24 {25 26 int n;27 while(~scanf("%d", &n))28 {29 long long sum = 0;30 for(int i = 1; i * i <= n; i++)31 {32 if(i * i == n) //这时只需要加一次33 {34 sum += ((long long)(Eular(i) * i));35 break;36 }37 if(n % i == 0) //这里例如就是Eular(2) * 6 和 Eular(6) * 2;38 {39 sum += ((long long)(Eular(i) * (n / i)));40 sum += ((long long)(Eular(n / i) * i));41 }42 }43 printf("%lld\n", sum);44 }45 }
NYOJ-569最大公约数之和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。