SPOJ LCMSUM (数论)

题意：对于 n，求出sigma (LCM (i , n))    n >=  i >=1。

思路：首先可以得到LCM (i , n) = n*i / gcd(i, n).

可以将n提取出来，也就是说现在要求sigma（i / gcd(i, n)）

可以发现gcd(i, n)是n的因子，数量不会太多，所以可以考虑枚举n的因子g。

将分母相同的项分为一类，也就是说，对于n的一个因子g，现在要求sigma（i/g）

也就是说所有跟n/g互素的数 的和。

这里有一个性质，对于 m >= 2，小于等于m且与m的互质的数的和为m * phi (m) / 2。

这比较好证明：

如果gcd (a , m) = 1那么gcd (m - a , m) = 1。所以所有的互质的数，可以两两分组。

那么分母为g的求和便是 n * phi(n / g) * n / g / 2

那么和就是n * phi(n / g) * n / g / 2。

这道题比较麻烦的是时间卡的紧，要枚举因子预处理出答案，注意这一点就好。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

const int MAXN = 1000100;
//const int INF = 0x3f3f3f3f;
int n;
int phi[MAXN];
LL ans[MAXN];
void init() {
	phi[1] = 1;
	for(int i = 2; i <= 1e6; i++) if(!phi[i]) {
		for(int j = i; j <= 1e6; j+=i) {
			if(!phi[j]) phi[j] = j;
			phi[j] = phi[j]/i*(i-1);
		}
	}
}
void init2() {
    for(int i = 1; i <= 1e6; i++) {
        for(int j = i; j <= 1e6; j+=i) {
            ans[j] += (LL)phi[i] * i >> 1;
        }
        ans[i] = (ans[i]+1)*i;
    }
}
int main() {
    //freopen("input.txt", "r", stdin);
	init();
	init2();
	int T;
	cin >> T;
	while(T--) {
		scanf("%d", &n);
		printf("%lld\n", ans[n]);
	}
    return 0;
}