[Sdoi2008]沙拉公主的困惑

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

solution

有用到的性质：

1.

if  gcd(x,y)==1，gcd(x+t*y，y)==1

证明：

假设x+t*y，y不互质

设p为y和x+t*y的一个公约数

那么有 (x+t*y)/p==0

           x/p==0&&t*y/p==0

但是既然p是y的一个质因子，x又和y互质，所以p肯定不是x的因子，即x/p!=0

所以假设不成立

2.

φ(N)=N*(1-1/p1)*(1-1/p2)*...*(1-1/pn)

根据性质1有：

因为m<=n

从1~m!有φ(m!)个答案，那么从m!+1~2*m!还是有φ(m!)个答案，以此类推

ans=φ(m!)* n!/m!

根据性质2

φ(i)=φ(i-1)*i  (i是合数)

        φ(i-1)*(i-1)  (i是质数)

所以只需要筛出质数，预处理出φ(m!)/m!和n!即可O(1)查询

(也可以预处理 (1-1/p1)*(1-1/p2)*...*(1-1/pn) 因为φ(m!)/m!把m!消了 )

(记得算一下内存)

某些大佬出了一组神奇数据：

1 100

3 2

mod是质数

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int N=10000066;

int T,mod,n,m;
int prime[N/3],cnt;
bool he[N+10];
ll phi[N+10],jie[N+10],ni[N+10];

void chu()
{
    for(int i=2;i<N;++i)
    {
        if(!he[i])
          prime[++cnt]=i;
        for(int j=1;j<=cnt&&(ll)prime[j]*(ll)i<N;++j)
        {
            he[prime[j]*i]=1;
            if(i%prime[j]==0)
              break;
        }
    }
    //prime[cnt+1]=0x7fffffff;
    
    //cout<<cnt<<endl;
    
    ni[1]=1;
    for(int i=2;i<N;++i)
    {
      ni[i]=(ll)(mod-mod/i)*ni[mod%i]%mod;
    }
    
    jie[1]=1;
    for(int i=2;i<N;++i)
    {
      jie[i]=jie[i-1]*ni[i]%mod;
      //if(jie[i]==0)
       // cout<<i<<endl;
    }
    
    //cout<<jie[N-100000]<<endl;
    
    //printf("jieni[2]=%lld
",jie[2]);
    
    phi[1]=1;
    phi[2]=1;
    for(int i=3;i<N;++i)
    {
        if(he[i])
          phi[i]=phi[i-1]*(ll)i%mod;
        else
          phi[i]=phi[i-1]*(ll)(i-1)%mod;
    }
    
    for(int i=1;i<N;++i)
      phi[i]=phi[i]*jie[i]%mod;
    
    for(int i=2;i<N;++i)
      jie[i]=jie[i-1]*(ll)i%mod;
}

int main(){
    
    //freopen("1.txt","r",stdin);
    
    scanf("%d%d",&T,&mod);
    chu();
    
    ll temp;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        
        //printf("jie[n]=%lld
",jie[n]);
        //printf("phi[m]=%lld
",phi[m]);
        
        temp=jie[n]*phi[m]%mod;
        printf("%lld
",temp);
    }
    return 0;
}