返回信息流题目要求10的8次方，要求好高啊，样例都跑了4秒。。希望大神赐教，指条明路。。拜谢
C. Goblin's Appreciation
时间限制 1000 ms 内存限制 65536 KB
题目描述
Your clan has been subjected to the harassment of the goblins. Your leader decided to fight back for peace. But the story is more complex than your imagination, reckoning with the numerous resources wasted in the war, the leader assigned you as the envoy to win the dignity.
Now you have arrived there, you find the goblins love math very much. They only appreciate the guys with high intellegence, so they give you a math problem, if you can solve it in 1s, they will appreciate you and protect your clan as a gift. For peace, just fighting!
They give you a lot of pairs of numbers, denoted by K,N. for every input, you should tell them the sum of k^gcd(i,n), for i = 1~n.
For the answer is so large, you can give them the answer mod 23333.
输入格式
Given T, the number of cases. Then, for next T lines, there are two numbers K,N.(1 <= k <= 10^4, 1 <= n <= 10^8)
输出格式
For every case, print one line, containing the answer mod 23333.
输入样例
3
3 4
2 6
100 50000000
输出样例
96
84
3014
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89283同步于 2016/3/26
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
热身赛3 C题求指教
RainVision
2016/3/26镜像同步10 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
枚举gcd，题目转换成\sigma f(gcd)*k^gcd\
其中f(gcd)即为[1,n]中与n的最大公约数为gcd的数的个数，易知，f(gcd) = Euler(n/gcd)
所以我们只需要快速幂和欧拉函数即可
时间复杂度是O(sqrt(n)*log(n))
【 在 RainVision 的大作中提到: 】
: 题目要求10的8次方，要求好高啊，样例都跑了4秒。。希望大神赐教，指条明路。。拜谢
: C. Goblin's Appreciation
: 时间限制 1000 ms 内存限制 65536 KB
: ...................
谢谢！！！
【 在 samuelwyf 的大作中提到: 】
: 枚举gcd，题目转换成\sigma f(gcd)*k^gcd\
: 其中f(gcd)即为[1,n]中与n的最大公约数为gcd的数的个数，易知，f(gcd) = Euler(n/gcd)
: 所以我们只
: .........
【 在 samuelwyf 的大作中提到: 】
: 枚举gcd，题目转换成\sigma f(gcd)*k^gcd\
: 其中f(gcd)即为[1,n]中与n的最大公约数为gcd的数的个数，易知，f(gcd) = Euler(n/gcd)
: 所以我们只需要快速幂和欧拉函数即可
: ...................
枚举gcd不一样还要乘上O(n)的复杂度吗？
【 在 b727787721 的大作中提到: 】
: 枚举gcd不一样还要乘上O(n)的复杂度吗？
应该是指枚举所有gcd的值，而不是枚举计算出所有1到n的gcd
是的
【 在 ykprocess 的大作中提到: 】
:
: 【 在 b727787721 的大作中提到: 】
: : 枚举gcd不一样还要乘上O(n)的复杂度吗？
: 应该是指枚举所有gcd的值，而不是枚举计算出所有1到n的gcd
: