题目 1481 [UVa 11426] 最大公约数之和——极限版II
2017-01-03 20:21:16
|
|
线性筛,隐式莫反(构造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))。 这真是智障,我用莫比乌斯函数求出来了欧拉函数- - |
|
|
|
单次O(输入的n)查询还是过了...
|
|
欧拉函数前缀和
O(n)预处理 + O(sqrt(n))单次询问 |
|
论大小号同时提交的后果......
然后...O(nlnn)的垃圾筛慢成翔啊......A不A全看评测机心情...... |
|
O(n)做法
|
|
模板就是硬
|
|
题目 1481 [UVa 11426] 最大公约数之和——极限版II
2015-08-03 20:07:55
|
|
样例更新了?好评!
|
|
谁出的这道题。。。。。。
调了一个小时,发现样例错了。。。。。。 出题人,我要跟你拼了! |
|
|
|
题目 1481 [UVa 11426] 最大公约数之和——极限版II
2014-01-15 19:59:09
|
|
回复 @cstdio :
我指的是预处理的复杂度是N*LOGN,每次询问时枚举因数再分块优化可以做到每次询问的复杂度为N^0.5(这里需要用欧拉函数预处理1到N范围内互质数对的个数),总复杂度为N*LOGN+T*N^0.5. |
|
|
|
题目 1481 [UVa 11426] 最大公约数之和——极限版II
2014-01-14 19:36:34
|
|
筛法求欧拉函数,最后求解时再分块优化。。类似HAOI2011问题B,可以做到O(N^0.5*t).
|
|
正确率被我刷低了
题目 1481 [UVa 11426] 最大公约数之和——极限版II
2014-01-14 18:01:57
|