Gravatar
Go灬Fire
积分:3414
提交:1738 / 3778
回复 @Mike is Fool :
可以证明phi(T)= sigma ( d | T )u( T / d )* d

Gravatar
FoolMike
积分:5206
提交:1165 / 2240
线性筛,隐式莫反(构造f函数的时候用的),分块,O(n)预处理,O(sqrt(n))查询
其中定义f(x)=(d|x)d*miu[x/d],不难证明f函数的积性,之后有假设1<=i,j<=n,ans=(1<=x<=n)(n/x)*(n/x)*f(x)(莫反的枚举变量交换一下),询问分块就好了。
不难证明,F(x)=(d|x)f(x)=x(莫比乌斯反演公式可证)
所以也可以杜教筛求f函数的前缀和,每次询问O(n^(2/3)),预处理O(n^(2/3))。
这真是智障,我用莫比乌斯函数求出来了欧拉函数- -

Gravatar
Hzoi_chairman
积分:2419
提交:931 / 2223

Gravatar
sxysxy
积分:2487
提交:603 / 1120
单次O(输入的n)查询还是过了...

Gravatar
‎MistyEye
积分:2487
提交:850 / 1904
欧拉函数前缀和
O(n)预处理 + O(sqrt(n))单次询问

Gravatar
AntiLeaf
积分:3396
提交:1527 / 4369
论大小号同时提交的后果......
然后...O(nlnn)的垃圾筛慢成翔啊......A不A全看评测机心情......

Gravatar
夜雨
积分:157
提交:33 / 75
O(n)做法

Gravatar
forever
积分:1322
提交:475 / 868
模板就是硬

Gravatar
<蒟蒻>我要喝豆奶
积分:848
提交:242 / 543
回复 @<大神养成>溪哥 :
。。。。。。ORZ

Gravatar
神利·代目
积分:3121
提交:803 / 1626
样例更新了?好评!

Gravatar
神利·代目
积分:3121
提交:803 / 1626
谁出的这道题。。。。。。
调了一个小时,发现样例错了。。。。。。
出题人,我要跟你拼了!

Gravatar
cstdio
积分:4748
提交:1198 / 2108
回复 @weizj :
高大上的解法……
由于T小,因此这道题在线回答更好,这个想法不错

Gravatar
C语言入门
积分:572
提交:125 / 374
回复 @cstdio :
好吧。。我打错了。。应该就是预处理复杂接近NLOGN的。。

Gravatar
C语言入门
积分:572
提交:125 / 374
回复 @cstdio :
我指的是预处理的复杂度是N*LOGN,每次询问时枚举因数再分块优化可以做到每次询问的复杂度为N^0.5(这里需要用欧拉函数预处理1到N范围内互质数对的个数),总复杂度为N*LOGN+T*N^0.5.

Gravatar
cstdio
积分:4748
提交:1198 / 2108
回复 @weizj :
求解,怎么做到的……筛法求欧拉函数不是O(nlogn)吗?

Gravatar
,
积分:425
提交:128 / 305
回复 @weizj :
好神奇的优化

Gravatar
C语言入门
积分:572
提交:125 / 374
筛法求欧拉函数,最后求解时再分块优化。。类似HAOI2011问题B,可以做到O(N^0.5*t).

Gravatar
,
积分:425
提交:128 / 305
正确率被我刷低了