BZOJ2186: [Sdoi2008]沙拉公主的困惑

好久没写题的总结了,这道题还是挺有意思的,写一下好了...
然而网上都说是SB题..
BZOJ2186
--------------------------------------------------------
 
要求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))
}
--------------------------------------------------------