python水题QAQ
def gcd (x,y):
if y>0:return gcd(y,x%y);
else:return x;

n=0;k=0;i=0;
ans=0;
n,k=raw_input().split(' ');
n=int(n);
k=int(k);
if n%2==1:ans = k**(n/2+1)*n;
else:ans=k**(n/2+1)*(n/2)+k**(n/2)*(n/2);
for i in range(1,n+1):ans+=k**(gcd(n,i));
print ans/(2*n);

测试数据 #0: Accepted, time = 31 ms, mem = 48880 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 48876 KiB, score = 10

测试数据 #2: Accepted, time = 31 ms, mem = 48876 KiB, score = 10

测试数据 #3: Accepted, time = 46 ms, mem = 48872 KiB, score = 10

测试数据 #4: Accepted, time = 46 ms, mem = 48876 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 48880 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 48876 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 48876 KiB, score = 10

测试数据 #8: Accepted, time = 62 ms, mem = 48880 KiB, score = 10

测试数据 #9: Accepted, time = 125 ms, mem = 48872 KiB, score = 10

Accepted, time = 433 ms, mem = 48880 KiB, score = 100

可以把M的0至N次幂预处理一下

蒟蒻想请教个问题，假如每个球都只有有限个，那么有方法求方案总数吗，如果有的话该怎样求呢？

第九个。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：166ms

1A~~~~~~~

POLYA+高精加法+高精乘法+高精除法

压了8位

从这题开始学 polya 计数法……

虽然A 了， 但是有一点不明白：

对于 n=2， m=2 翻转置换 有 2 个 ， 但是其中一个 和 “旋转0位“的置换

都是 自身~自身 的 置换，换句话说 这 两个 置换 完全相同。

不 去重 的 运算 结果 是 对 的， 去重 反而 错 了 ……

WHY？？？

补充 楼下 的 算法： 对于 翻转置换 其实 只 需要 一句 ：

if odd(n) then inc(b[(n+1)shr 1],n)

else

begin

inc(b[n shr 1+1],n shr 1);

inc(b[n shr 1],n shr 1);

end;

//b[i]表示 有 多少 个 m^i……

n=2*k+1时，有n 个对称轴（过一个端点），每个 对应 的置换 有 k+1 个 循环节；

n=2*k时， 有 k 个对称轴（过两个端点），循环节为 k+1

还有 k 个对称轴（不过端点）， 循环节为 k

原题：http://acm.pku.edu.cn/JudgeOnline/problem?id=2409

本题是上面那玩意儿的高精度版。

这题就是用轮换和翻转生成置换，

对于第i种置换累加m^ci ,ci是循环节数目，

简单轮换的循环数是gcd(i,m)，

带翻转的我使用并查集算的。

最后把答案除以2*n即可。

当然。。这题卡常数。。我有两个优化：

1. 对于m^ci，因为本人懒得用快速幂，所以我把所有的m的幂方按照ci归类。

hash[x]表示有多少个m^ci累加，因为ci种数很少，优化效果明显。

2. 压位，因为vijos可以用int64，所以10^6进制压一下。

我是真沙茶，你是假沙茶

对楼下说，这题不是我这种沙茶出得……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 119ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 416ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：654ms

JZP神牛出的这道题，适合Pólya原理的初学者，比如说我，运用Pólya原理，加上高精度时四位一压，可以轻松AC。

我就一次AC了。

AC了。艰难的过程啊。。我太弱了。太菜了。

小号AC了这道SB题

晕……看来自己真的过时了……

水

polya定理题。。旋转和反转分别对应置换。

垃圾题，管理员快删。。。

polya 怎么办啊~~~？？很囧人啊~~

polya定理...

vijos机子真快,在我家铁定TLE.高精没压位还用结构体写的

傻×题怎么搞上来了？

还有为什么这种傻×题你们的程序都这么慢？

大家好～～～～

菜鸟飘过。。。