lcm 过大无法枚举，考虑枚举gcd
对于一组，有，且
记
根据定义，若，则
因此
枚举所有的k
则
复杂度
直到有一天我被卡了，才发现有复杂度更低的做法
继续化简上式
好吧没啥区别
可以，回答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#define LL long long
const int N=1000050;
int phi[N],prime[N],cnt=0;
LL f[N];
inline int ()
{
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("%lldn",f[read()]);
return 0;
}
|
近期评论