1040?最大公約數(shù)之和 題目來(lái)源：?rihkddd 基準(zhǔn)時(shí)間限制：1?秒 空間限制：131072?KB 分值:?80?難度：5級(jí)算法題 ?收藏 ?關(guān)注 給出一個(gè)n，求1-n這n個(gè)數(shù)，同n的最大公約數(shù)的和。比如：n = 6 1,2,3,4,5,6 同6的最大公約數(shù)分別為1,2,3,2,1,6，加在一起 = 15 Input 1個(gè)數(shù)N(N?<=?10^9) Output 公約數(shù)之和 Input示例 6 Output示例 15 思路： 目的是求∑（i= 1，n） gcd( i , n )； gcd( i , n ) = x，表示x是n的因子。稍作變形gcd( i / x , n / x) = 1， 看到這個(gè)式子可以想到歐拉函數(shù)，也就是求比n/x小的與其互質(zhì)的個(gè)數(shù)。 因?yàn)檫@些書和n/x互質(zhì)，乘上x(chóng)后與n的最大公約數(shù)只有x。 也就是說(shuō)我們先求出每個(gè)因子，然后計(jì)算每個(gè)因子有多少貢獻(xiàn)即可。 /** Author: sweat123* Created Time: 2016/6/27 14:01:46* File Name: main.cpp*/ #include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<string> #include<vector> #include<cstdio> #include<time.h> #include<cstring> #include<iostream> #include<algorithm> #define INF 1<<30 #define MOD 1000000007 #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pi acos(-1.0) using namespace std; const int MAXN = 1000000; int n; ll ef(int n) { ll cnt = n; int i; for(i = 2; i * i <= n; i++){ if(n % i == 0) { cnt -= cnt / i; // (x-x/p1) *(1-1/p2)*(1-1/p3)*(1-1/p4).....while(n % i == 0) n /= i; } }if(n > 1) cnt -= cnt / n;return cnt; } int main(){while(~scanf("%d",&n)){ll ans = 0;for(int i = 1; i <= (int)sqrt(n); i++){if(n % i == 0){ans += ef(n / i) * i;if(n / i != i){ans += ef(i) * (n / i); }}} printf("%lld\n",ans);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sweat123/p/5620086.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的51nod 1040最大公约数和（欧拉函数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。