BZOJ2186 Sdoi2008 沙拉公主的困惑

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

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 5007  Solved: 1726
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

1 11
4 2

Sample Output

1

数据范围：
对于100%的数据，1 < = N , M < = 10000000

HINT

Source

显然题目是求phi（m!) * ( n! / m!)

phi (m!) = m! * (p-1)/p p是m!的质因数

所以就是求 n! * (p-1)/p p是m!的质因数

我们与处理出来1-10000000的素数以及1-10000000的逆元

用exgcd求的话复杂度应该是nlogn的

逆元有线性求法

比如在模mod意义下

ine[i]=(mod-ine[mod%i]*mod/i+mod)%mod

#include <bits/stdc++.h>
#define  ll long long
using namespace std;
inline int read(){
    int x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)) {
    if(ch=='-') f-1;ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-'0';ch=getchar();
    }
    return x*f;
}
const int MAXN=1e7+10;
namespace zhangenming{
    int ine[MAXN+100]={},ans[MAXN+100]={},prime[MAXN+100],top=0,is_prime[MAXN+100]={},fac[MAXN+100]={},n,m,T,R;
    //ine[i]表示i的逆元；fac[i]表示i的阶乘 
    void ouler_shai(){
        for(int i=2;i<=MAXN;i++){
            if(!is_prime[i]){
                prime[++top]=i;
            }
            for(int j=1;j<=top&&i*prime[j]<=MAXN;j++){
                is_prime[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void pre(){
        ouler_shai();
        fac[1]=1;
        ine[1]=1;
        for(int i=2;i<=MAXN;i++){
            fac[i]=(ll)fac[i-1]*i%R;
        }
        for(int i=2;i<=MAXN&&i<R;i++){
            ine[i]=(R-(ll)R/i*ine[R%i]%R);
        }
        ans[1]=1;
        for(int i=2;i<=MAXN;i++){
            ans[i]=ans[i-1];
            if(!is_prime[i]) ans[i]=(ll)ans[i]*(i-1)%R*ine[i%R]%R;
        }
    }
    void solve(){
     T=read();R=read();
     pre();
     while(T--){
         n=read();m=read();
         printf("%d
",(ll)fac[n]*ans[m]%R);
     }    
    }
}
int main(){
    using namespace zhangenming;
    solve();
    return 0;
}