题意:
分析:
挺经典的用 (varphi) 反演的题
[displaystyle
sum_{i=1}^nlcm(i,n)\
=sum_{i=1}^nfrac{in}{gcd(i,n)}\
=sum_{i=1}^nsum_dfrac{in}{d imes[gcd(i,n)==d]}\
=sum_{i=1}^{lfloor{frac{n}{d}}
floor}sum_dfrac{idn}{d imes[gcd(i,n)==1]}\
=nsum_{d|n}sum_{i=1}^{lfloor{frac{n}{d}}
floor}i[gcd(i,frac{n}{d})==1]\
=nsum_{d|n}sum_{i=1}^d i[gcd(i,d)==1]\
]
其中 (displaystyle sum_{i=1}^d i[gcd(i,d)==1]) 等价于 (frac{d*varphi(d)}{2})
证明:
(forall gcd(i,n)==1)
存在 (gcd(n-i,n)==1)
所以必定存在两个与 (n) 互质的数和值为 (n)
QED.
总复杂度 (O(nlog )) 预处理时需要调和级数,但是要特判 (d=1) 时答案为 $1 $
另解:
[displaystyle
sum_{i=1}^nfrac{in}{gcd(i,n)}\
=frac{1}{2}(sum_{i=1}^{n-1}frac{in}{gcd(i,n)}+sum_{i=n-1}^1frac{in}{gcd(i,n)})+n\
=frac{1}{2}sum_{i=1}^{n-1}frac{n^2}{gcd(i,n)}+n\
=frac{1}{2}sum_{d|n}frac{n^2}{d} imesvarphi(lfloorfrac{n}{d}
floor)+n
]
最后一步枚举 (d) 时乘的 (varphi(lfloor{frac{n}{d}} floor)) 相当于是 (gcd(i,n)==d) 的个数
证明:
(gcd(i,n)==d o gcd(frac{i}{d},frac{n}{d})==1) 等价于 (varphi)
代码:
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register
using namespace std;
namespace zzc
{
typedef long long ll;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 1e6+5;
ll n,t,cnt;
ll p[maxn],phi[maxn],f[maxn];
bool vis[maxn];
void init()
{
phi[1]=1;
for(int i=2;i<=1000000;i++)
{
if(!vis[i])
{
p[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*p[j]<=1000000;j++)
{
vis[i*p[j]]=true;
if(i%p[j]==0)
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
for(int i=1;i<=1000000;i++) for(int j=i;j<=1000000;j+=i) f[j]+=phi[i]*i/2;
for(int i=1;i<=1000000;i++) f[i]=i*f[i]+i;
}
void work()
{
ll a;
init();
t=read();
while(t--)
{
a=read();
printf("%lld
",f[a]);
}
}
}
int main()
{
zzc::work();
return 0;
}