【洛谷 P2303】 [SDOi2012]Longge的问题（欧拉函数）

题目链接

题意：求\(\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}{d}\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;

}

巴特西

【洛谷 P2303】 [SDOi2012]Longge的问题（欧拉函数）

最新文章

热门文章

巴特西

【洛谷 P2303】 [SDOi2012]Longge的问题 （欧拉函数）

最新文章

热门文章

【洛谷 P2303】 [SDOi2012]Longge的问题（欧拉函数）