GCD - Extreme (II)

题目

图片说明
题意很简单，就是给定一个N，让求出N范围内的所有gcd（i,j）的和，
时限：10s

分析

当我看见这题是时限我就觉得不简单，同时数据量N太大，都到4e6了。但是这题N范围内的答案都需要去求，因为这题没法在线处理，所以考虑暴力的优化。我们需要去枚举什么变量,可以发现两个数去找gcd是个非常麻烦的事，因为a的情况xb的情况的数量级就已经爆炸了。所以我们可以考虑枚举gcd去找a，b。

关于gcd，我们可以知道:是互质的，而互质我们可以想到欧拉函数。假如一个数b，b/c = a ，那么与a互质的共有E[a]个数，这些数乘以c之后与b的gcd就是c。所以我们就可以枚举gcd，然后再枚举gcd的倍数，然后打个表，计算一下前缀和即可。具体看代码。

AC代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
const ll maxn = 4e6+10;

ll N;
ll E[maxn],sum[maxn];

void init()
{
    E[1] = 1;
    for(int i=2;i<maxn;i++){ //预处理欧拉函数值
        if(!E[i])
            for(int j=i;j<maxn;j+=i){
                if(!E[j]) E[j]=j;
                E[j] = E[j]/i*(i-1);
            }
    }
    for(ll i = 1;i<maxn;i++){ //枚举gcd
        for(ll j = 2*i;j<maxn;j+=i){ //枚举gcd的倍数
            sum[j] += E[j/i]*i;
        }
    }
    for(ll i =2;i<maxn;i++) sum[i] += sum[i-1]; //计算前缀和
}
int main(){
    init();
    while(scanf("%lld",&N)){
        if(N == 0) break;
        printf("%lld\n",sum[N]);
    }

    return 0;
}