题目
题目描述
最近，华东交通大学ACM训练基地的老阿姨被一个数学问题困扰了很久，她希望你能够帮她解决这个问题。
这个数学问题是这样的，给你一个N,要求你计算
gcd(a,b)表示a和b的最大公约数
输入描述
多组输入，每行一个整数n(1<=n<=10^14)。
输出描述
每行一个整数，表示答案。由于答案会很大你要对1000000007取模。
示例1
输入
4
10
输出
6
35
说明
样例一，2+4=6。
样例二，2+4+5+6+8+10=35。
题解
知识点：欧拉函数，GCD与LCM。
简单推一下式子：
\[\begin{aligned}
\sum_{i=1}^n i[\gcd(i,n) \neq 1] &= \sum_{i=1}^n i(1-[\gcd(i,n) = 1])\\
&= \frac{n(n+1)}{2} - \sum_{i=1}^n i[\gcd(i,n) = 1]\\
&= \frac{n(n+1)}{2} - \frac{n\varphi(n) + [n = 1]}{2}
\end{aligned}
\]
第二行后面一项表示 \([1,n]\) 中和 \(n\) 互质的数的和，可以用欧拉函数 \(O(1)\) 得到。
简单证明一下：与 \(n(n\geq3)\) 互质的数总是成对出现的 \(x,n-x\) ，因此每一对的和都是 \(n\) ，所以答案就是 \(\varphi(n)\) 乘以 \(\dfrac{n}{2}\) 。特别地， \(n = 2\) 时答案和公式一样，\(n=1\) 时加一个简单修正即可。
另外，这个证明也可以看出来，与 \(n(n\geq 3)\) 互质的数总是偶数个。
其中欧拉函数每个需要单独求，即需要对 \(n\) 分解质因数。
时间复杂度 \(O(\sqrt n)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
const int P = 1e9 + 7;
ll euler_one(ll n) {
ll ans = n;
for (ll i = 2;i * i <= n;i++) {
if (!(n % i)) {
ans = ans / i * (i - 1);
while (!(n % i)) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll n;
while (cin >> n) cout << int(((i128)n * (n + 1) / 2 - ((i128)n * euler_one(n) + (n == 1)) / 2) % P) << '\n';
return 0;
}