題目鏈接
題意：求\(\sum_{i=1}^{n}\gcd(i,n)\)

首先可以肯定，\(\gcd(i,n)|n\)。

所以設\(t(x)\)表示\(gcd(i,n)=x\)的\(i\)的個數。

那么答案很顯然就是\(\sum_{d|n}t(d)*d\)。

那么\(t(x)\)怎么求呢。

\[t(x)=\sum_{i=1}^{n}[\gcd(i,n)=x]\]
因為若\(\gcd(x,y)=1\),則有\(\gcd(xk,yk)=k\)。
所以
\[t(x)=\sum_{i=1}^{n}[\gcd(i,n)=x]=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}[\gcd(i,\lfloor\frac{n}{x}\rfloor)=1]=\phi(\lfloor\frac{n}{x}\rfloor)\]
所以最終答案就是\(\sum_{d|n}[\phi(\lfloor\frac{n}ze8trgl8bvbq\rfloor)*d]\)

我們可以在\(O(\sqrt n)\)的時間復雜度內求出\(n\)的所有約數，約數個數是\(\log n\)級別的，求\(\phi\)是\(O(\sqrt n)\)的時間復雜度，所以總時間復雜度\(O(\log n\sqrt n)\)

#include <cstdio> #include <cmath> using namespace std; typedef long long ll; ll n; ll phi(ll x){int s = sqrt(x); ll ans = x;for(int i = 2; i <= s && x != 1; ++i)if(!(x % i)){ans = ans / i * (i - 1);while(!(x % i))x /= i;}if(x != 1) ans = ans / x * (x - 1);return ans; } int main(){scanf("%lld", &n);int i; ll ans = 0;for(i = 1; (ll)i * i < n; ++i)if(!(n % i))ans += phi(n / i) * i + (n / i) * phi(i);if(i * i == n) ans += phi(i) * i;printf("%lld\n", ans);return 0; }

轉載于:https://www.cnblogs.com/Qihoo360/p/9777286.html

總結

以上是生活随笔為你收集整理的【洛谷 P2303】 [SDOi2012]Longge的问题 （欧拉函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。