BZOJ2186: [Sdoi2008]沙拉公主的困惑
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
好久没写题的总结了，这道题还是挺有意思的，写一下好了...
然而网上都说是SB题..
--------------------------------------------------------
要求1~N!内与M!互质的数个数
也就是gcd(x,M!)=1的个数
由更相减损术的正确性定理:gcd(x,y) = gcd(x+y,y)
因此若x与M!互质，那么x+M!也与M!互质
所以我们只需要知道M!以内与M!互质的数个数，乘以N!/M!即可
而M!内与M!互质的数个数就是phi(M!)
因此要求phi(M!)以及M!的逆元
M!的逆元就是pow(M!,p-2)
而phi(a) = a * (phi(p1) / p1) * (phi(p2) / p2) * ... * (phi(pk) / pk)
其中p1,p2..pk是a的质因数（重复的只算一次）,而phi(M!)的质因数就是小于它的所有质数，因此对所有质数求一个(phi
(p)/ p)的前缀积然后预处理出来就可以了
--------------------------------------------------------
顺便总结一下线性求逆元以及阶乘逆元的方法好了:
设f(i)表示i的逆元
有:
f(i!) = f((i+1)!) * (i+1)
f(i) = f(p / i) * (p - (p % i))
{
在质数p的模域下，有
由：x = k
则([p/i] * i + k) = 0 （这里[]表示取下整）
因此[p/i] * i = -k = p-k
因此i^-1 = [p/i]^1 * (p-k)
而k=p%i
因此f(i) = f(p / i) * (p - (p % i))
}
--------------------------------------------------------
评论 (0)
