描述

求Σgcd(i, n),?0<N≤2^32

分析

• 直接求是不行的, 可以分析滿足gcd(i, n) = j 的 i 有多少個(gè), 再用 j 乘上這個(gè)個(gè)數(shù).
• 如果gcd(i, n) = j, 那么gcd(i/j, n/j) = 1, 又由于i≤n, 所以gcd(i/j, n/j) = 1的個(gè)數(shù)就是不超過n/j并與n/j互質(zhì)的數(shù)的個(gè)數(shù), 即φ(n/j).
• 所以Σgcd(i, n) = j *?φ(n/j), ?j | n.
• 枚舉n的因子j, 統(tǒng)計(jì) j*φ(n/j) + n/j?*?φ(j). ?O(sqrt(n) * sqrt(sqrt(n)))
• 還有種更簡(jiǎn)單的方法, 但是沒看懂

代碼
#include #include using namespace std; typedef long long int lli;int phi(int n) {int ret = n;int m = (int)(sqrt(n) + 0.5);for(int i = 2; i <= m; i++) if(n % i == 0) {ret = ret / i * (i-1);while(n % i == 0) n /= i;}if(n > 1) ret = ret / n * (n-1);return ret; }int main() {lli n;scanf("%lld", &n);lli m = (lli)(sqrt(n) + 0.5);lli ans = 0;for(lli i = 1; i <= m; i++) if(n%i == 0) {ans += i * phi(n/i);if(i*i < n) ans += n/i * phi(i);}printf("%lld\n", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ-2705-Longge的游戏-SDOI2012-欧拉函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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