洛谷P1891 疯狂LCM

lcm 过大无法枚举，考虑枚举gcd
对于一组$gcd\left ( x,n \right )=k$，有$gcd\left ( \frac{x}{k},\frac{n}{k} \right )=1$，且$lcm\left(x,n\right)=\frac{xn}{k}$
记

$$f\left [ k \right ]=\sum_{i=1}^{k}i\left [ gcd\left ( i,k \right )=1 \right ]$$

根据定义，若$gcd\left ( x,n \right )=1$，则$gcd\left ( n-x,n \right )=1$
因此

$$f\left [ k \right ]= \frac{k*\varphi\left [ k \right ]}{2}$$

枚举所有的k
则

$$\sum lcm\left ( x,n \right )=k*\frac{n}{k}*f\left [ \frac{n}{k} \right ]\left ( k|n,gcd\left ( x,n \right )=k \right )$$

复杂度$O\left ( T\sqrt{N} \right )$

直到有一天我被卡了，才发现有复杂度更低的做法
继续化简上式

$$\sum lcm\left ( x,n \right )=n*f\left [ \frac{n}{k} \right ]\left ( k|n,gcd\left ( x,n \right )=k \right )$$

好吧没啥区别

$$\sum_{i=1}^{n}lcm(i,n)=\sum _{d\mid n}f\left [ d \right ]*n$$

可以$O\left ( NlogN \right )$，$O\left (1 \right )$回答

#include<cstdio>
#define LL long long
const int N=1000050;
int phi[N],prime[N],cnt=0;
LL f[N];
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') {t=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*t;
}
void init()
{
    for(int i=2;i<N;i++)
    {
        if (!phi[i]) prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++)
        {
            if ((LL)i*prime[j]>N) break;
            if (i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=2;i<N;i++)
    	for(int j=i;j<N;j+=i)
            f[j]+=(LL)phi[i]*i/2*j;
    for(int i=1;i<N;i++) f[i]+=i;
}
int main()
{
    init();
    int T=read();
    while (T--) printf("%lld\n",f[read()]);
    return 0;
}