P2303 [SDOI2012] Longge 的问题

输入一个数据 $n$，求

$\qquad \qquad \qquad \sum_{i=1}^{n}\gcd(i, n)$

其中 $n$可以达到 $2^{32}$

题解：

$\begin{aligned} \qquad\qquad\qquad 原式 &= \sum_{i=1}^{n}\gcd(i, n)\\ &= \sum_{d|n}^{d} \cdot \sum_{i=1}^{n}[\gcd(i, n)=d](枚举公约数, []为单位函数)\\ &= \boxed{\sum_{d|n}^{d} \cdot \sum_{i=1}^{ \lfloor {n/d} \rfloor } [\gcd(i, \frac{n}{d}) = 1] }\\&= \sum_{d|n}^{d} \cdot \phi(\lfloor \frac{n}{d} \rfloor ) \end{aligned}$

$枚举公约数即可$

#include <bits/stdc++.h>
using namespace std;typedef long long LL;LL phi(LL n) {LL res = n;for (LL i = 2; i * i <= n; i++) {if (n % i == 0) res = res / i * (i - 1);while (n % i == 0) n /= i;}if (n > 1) res = res / n * (n - 1);return res;
}LL cal(LL n) {LL res = 0, i = 1;for (i = 1; i * i < n; i++) {if (n % i == 0) {res += i * phi(n / i);res += n / i * phi(i);}}if (i * i == n) res += i * phi(i);return res;
}int main() {LL x;cin >> x;cout << cal(x) << endl;return 0;
}