【bzoj2186】[Sdoi2008]沙拉公主的困惑 欧拉函数

题目描述

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。

输入

第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n

输出

共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值

样例输入

1 11
4 2

样例输出

1

---

题解

欧拉函数

如果a与m互质，那么a+m与m一定也互质，a+2m与m一定也互质，a+(k-1)m与m一定也互质。

所以km中与m互质的数是m中与m互质的数的k倍，即kφ(m)

注意到这里边N!是M!的倍数，所以所求即为N!/M!*φ(M!)

而φ(M!)=M!*∏(p-1)/p，p为M的质因子，所以所求就是N!/∏p，我们只需要预处理出1/∏p即可。这里我们需要筛素数和求逆元。

然后学到了一种O(n)递推求逆元的方法：ine[i]=(R-R/i*ine[R%i]%R)

这样就能够在O(n)时间内预处理出1/∏p，最后再乘上N!即可。

#include <cstdio>

#define N 10000010

typedef long long ll;

const int n = 10000000;

int fac[N] , ine[N] , ans[N] , phi[N] , prime[N] , tot;

bool np[N];

int main()

{

    int T , p , i , j , x , y;

    scanf("%d%d" , &T , &p);

    fac[1] = phi[1] = ine[1] = ans[1] = 1;

    for(i = 2 ; i <= n ; i ++ )

    {

        fac[i] = (ll)fac[i - 1] * i % p , ine[i] = (ll)(p - p / i) * ine[p % i] % p , ans[i] = ans[i - 1];

        if(!np[i]) phi[i] = i - 1 , ans[i] = (ll)ans[i] * (i - 1) % p * ine[i % p] % p , prime[++tot] = i;

        for(j = 1 ; j <= tot && i * prime[j] <= n ; j ++ )

        {

            np[i * prime[j]] = 1;

            if(i % prime[j] == 0)

            {

                phi[i * prime[j]] = phi[i] * prime[j];

                break;

            }

            else phi[i * prime[j]] = phi[i] * (prime[j] - 1);

        }

    }

    while(T -- ) scanf("%d%d" , &x , &y) , printf("%lld\n" , (ll)fac[x] * ans[y] % p);

    return 0;

}