1040 最大公约数之和
- 1 秒
- 131,072 KB
- 80 分
- 5 级题
给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15
收起
输入
1个数N(N <= 10^9)输出
公约数之和输入样例
6输出样例
15题目很简单，我们可以知道一个数的gcd一定是这个数的因子，现在我们来观察，比如15
1,2,4,7,8,11,13,14 这几个数和15的gcd都是1
3,6,9,12 这几个数和15的gcd都是3
5,10 这几个数和15的gcd都是5
15 这个数和15的gcd都是15
所以gcd之和是1 * 8 + 3 * 4 + 2 * 5 + 1 * 15 = 45
我们可以枚举因子i，那么gcd(x,n) = i ，假如gcd(i,n) = x有y个，那么i这个因子所做的贡献和就是y * i
又∵gcd(i,n) = x ∴gcd(n / i,x / i) = 1 因为x是n的约数，也是i的倍数，那么问题现在就转变成，枚举i，来求1到n / i中与n / i 互质的数有多少个，用欧拉函数算即可 （突然发现自己一直保存的phi的模板出锅了，我把res写成x了，找了一万年的错误）
#include <bits/stdc++.h>
#include <time.h>
#define first fi
#define second seusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 600 ;
const ll mod = 1e9 + 7;
inline int sign(db a) {return a < -eps ? -1 : a > eps;
}
inline int cmp(db a,db b) {return sign(a - b);
}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(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;}
ll c,n,k;
int main() {ios::sync_with_stdio(false);while(cin >> n) {ll ans = 0;for(ll i = 1; i * i <= n; i++) {if(n % i == 0) {ans += i * phi(n / i) ;if(i != n / i)ans += (n / i) * phi(i);}}cout << ans << endl;}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}