BZOJ2226 & SPOJ5971：LCMSum——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=2226

题目大意：给定一个n，求lcm(1,n)+lcm(2,n)+……+lcm(n,n)。

——————————————————————————————

如果是刚做完[SDOI2012]Longge的问题的话这道题应该能轻松一些。

显然答案可以转化为∑n*i/gcd(n,i)。

设k=gcd(n,i)，则可以转化为∑n*i/k(k|n且gcd(n,i)=k)，然后变成n*(∑i/k)(k|n且gcd(n,i)=k)。

又因为gcd(n/k,i/k)=1，所以对于一个k，∑i/k就是与n/k互质的数的和。

而对于一个数n，求与n互质的数的和=n*phi(n)/2。

于是这题我们就做完了。

PS：秉承着万恶的SPOJ题的尿性，这题有点卡常数。

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

ll phi[N],su[N];

bool he[N];

void Euler(int n){

    int tot=;

    phi[]=;

    for(int i=;i<=n;i++){

    if(!he[i]){

        su[++tot]=i;

        phi[i]=i-;

    }

    for(int j=;j<=tot;j++){

        if(i*su[j]>=n)break;

        he[i*su[j]]=;

        if(i%su[j]==){

        phi[i*su[j]]=phi[i]*su[j];break;

        }

        else phi[i*su[j]]=phi[i]*(su[j]-);

    }

    }

    return;

}

int main(){

    Euler();

    int t;

    scanf("%d",&t);

    while(t--){

    int n;ll ans=;

    scanf("%d",&n);

    for(int i=;i*i<=n;i++){

        if(n%i)continue;

        int k=n/i;

        ans+=(ll)(phi[k]*k+)>>;

        if(i*i<n)ans+=(ll)(phi[i]*i+)>>;

    }

    printf("%lld\n",ans*n);

    }

    return ;

}