题目链接
题意:
求 <mstyle displaystyle="true" scriptlevel="0"> <munderover> ∑ i = 1 n </munderover> <munderover> ∑ j = 1 i </munderover> g c d ( i , j ) </mstyle> \displaystyle\sum_{i = 1}^{n}\sum_{j = 1}^{i}gcd(i,j) i=1∑n​j=1∑i​gcd(i,j)
思路:
对于gcd(x, y)假设我们知道gcd(x,y) = c，我们也可以得到gcd(x/c, y/c) = 1.也就是说x/c与y/c互质。
那我们可以枚举枚举一个数(设为n)的所有因子(设为c)，然后算出有多少满足:gcd(n, x) = c => gcd(n/c, x/c) = 1。其实就是在算与n/c互质的个数，用欧拉函数搞一搞就行了。
所以设f(n)为 <mstyle displaystyle="true" scriptlevel="0"> <munderover> ∑ i = 1 n </munderover> i ∗ p h i [ n / i ] </mstyle> \displaystyle\sum_{i = 1}^{n}{i*phi[n/i]} i=1∑n​i∗phi[n/i]phi[i]表示在n/i内与i互质的个数。那么res就为 <mstyle displaystyle="true" scriptlevel="0"> <munderover> ∑ i = 1 n </munderover> f ( i ) </mstyle> \displaystyle\sum_{i = 1}^{n}{f(i)} i=1∑n​f(i)。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn =4e6+5;
typedef long long  ll;
ll sum[maxn];
int f[maxn], n;
int euler[maxn];
void geteuler() {
	euler[1] = 1;
	for(int i = 2; i < maxn; i++) {
		if(!euler[i])
			for(int j = i; j < maxn; j+=i) {
				if(!euler[j])
					euler[j] = j;
				euler[j] = euler[j]/i*(i-1);
			}
	}
}
int main() {
	geteuler();
	for(int i = 1; i <= (maxn>>1); i++) {
		for(int j = i*2; j < maxn; j += i) {
			f[j] += i*euler[j/i];
		}
	}
	for(int i = 1; i < maxn; i++) {
		sum[i] = sum[i-1]+f[i];
	}
    while(scanf("%d", &n) == 1 && n) {
    	printf("%lld\n", sum[n]);
    }
    return 0;
}