UVA 11426 GCD - Extreme (II)

题目链接:点我

题目

---

题意:

给你一个数n,求前n个数中任意两个数的 最小公倍数的和,

思路:

我们知道gcd(i, x) = t 可以得到gcd( i / t, x / t) = 1,所以我们只需要求与其互质对的数的个数,如何乘以i就可以了.

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;

typedef long long LL;
const int maxn = 4000000+10;
int phi[maxn];
LL a[maxn];

void init(){
    for(int i = 1; i < maxn; ++i)
        phi[i] = i;
    for(int i= 2; i < maxn; ++i){
        if(phi[i] == i){
            for(int j = i; j < maxn; j += i)
                phi[j] =phi[j] -  phi[j] / i;
        }for(int j = 1; i * j < maxn ;++j)
            a[i * j] += j * phi[i];
    }for(int i = 1; i < maxn;++i)
        a[i] += a[i-1];
}

int main(){
    init();
    int n;
    while(scanf("%d", &n), n){
        printf("%lld\n",a[n]);
    } return 0;
}