[BZOJ]Longge的问题[SDOI2012]

题目背景

SDOi2012

题目描述

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出$$\sum _{i=1} ^n gcd(i, N)$$。

输入输出格式

输入格式

一个整数，为N。

输出格式

一个整数，为所求的答案。

输入输出样例

输入样例

输出样例

说明

对于60%的数据，$$0<N \leq 2^{16}$$

对于100%的数据，$$0<N \leq 2^{32}$$

思路

数论

题意：求$$\sum _{i=1} ^n gcd(i,n)$$

设$$t(x)$$表示$$1到N中最大公约数为x的个数$$,即：

$$t(x)=\sum _{i=1} ^n [gcd(i,N)=x]=[gcd(i,\left \lfloor \frac{N}{x} \right \rfloor)=1]$$

$$ \therefore t(x)=\phi(\left \lfloor \frac{N}{x} \right \rfloor)$$

$$\sum {i=1} ^N gcd(i,N)=\sum {d|N} \sum {i=1} ^{\left \lfloor \frac{N}{d} \right \rfloor } (d \cdot \phi(\left \lfloor \frac{N}{d} \right \rfloor))=\sum {d|N}d \cdot \phi(\left \lfloor \frac{N}{d} \right \rfloor)$$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

ll n, ans = 0;

ll getphi(ll x)
{
    ll res = x;
    for (ll i = 2; i*i <= x; i++)
    {
        if (x%i==0)    res = res / i*(i - 1);
        while (x%i==0) x / = i;
    }
    if (x > 1)    res = res / x*(x - 1);
    return res;
}

int main()
{
    scanf("%lld", &n);
    ll i = 1;
    for (; i*i < n; i++)
    {
        if (n%i==0)    ans += i*getphi(n / i) + getphi(i)*(n / i);
    }
    if (i*i == n)    ans += i*getphi(i);
    printf("%lld\n", ans);
}

[BZOJ]Longge的问题