%%%峰哥ZYF
这题用的是burnside
ans=在每个置换群下不动的方案数之和除以置换数
这题有个难点在取模
关于对p（p为素数）取模（涉及到了除法），我总结了两种方法：
已知x mop p=y，要求x/z mod p=？
大体思路是利用乘法逆，将/z转换成*z的逆元即可
一、利用费马小定理
z^p-1 mod p=1
所以z的逆元=power_mod（z,p-2,p）
二、利用拓展欧几里德算法，即exgcd（z，p，x，y）
while x<0 do inc(x,p)
事实上，这也是乘法逆的思想
exgcd（z，p，x，y） 这实际上是在解同余方程zx mod p=1
x不就是z的逆元吗
但是当p不是素数时，应该怎么办呢？
在做noi2002robot的时候，我运用了一种特殊的方法，最后需要求x>>1 mod p=?
我在过程中始终对p取模，到最后感觉做不下去了
后来我灵机一动，想到了多取一位 在过程中mod 10p
这样 最后输出的时候再mod p 答案就正确了
不知道这样的方法能否应用在更广泛的地方……
ps:刚才试了一下此题
在过程中一直对m*p取模，最后ans div m 再对p取模，竟然AC了
原理在哪里？
评论 (0)
