[SDOI2008]沙拉公主的困惑线性筛_欧拉函数_逆元

Code:

#include<cstdio>

using namespace std;

typedef long long ll;

const int maxn=10000000+1;

long long mod;

ll   fac[maxn];

ll  inv[maxn];

ll  anss[maxn];

int cnt,prime[maxn];

bool vis[maxn];

ll pow(ll base,ll k)

{

    ll ans=1;

    while(k)

    {

        if(k&1)

            ans=(ll)(ans*base)%mod;

        k/=2;

        base=(ll)(base*base)%mod;

    }

    return ans;

}

ll get_inv(ll a){return pow(a,mod-2);}

void init()

{

    fac[1]=1;

    inv[1]=1;

    for(int i=2;i<maxn;++i)

    {

        fac[i]=(fac[i-1]*i)%mod;

        if(!vis[i])prime[++cnt]=i,inv[i]=get_inv(i);

        for(int j=1;j<=cnt&&prime[j]*i<maxn;++j)

        {

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

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

        }

    }

    anss[1]=1;

    for(int i=2;i<maxn;++i)                         //找M

    {

    	if(!vis[i])

    	{

    		anss[i]=(anss[i-1]*(i-1))%mod;

    		anss[i]=(anss[i]*inv[i])%mod;

    	}

    	else anss[i]=anss[i-1];

    }

}

int main()

{

    int T;

    scanf("%d %lld",&T,&mod);

    init();

    while(T--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        ll ans;

        ans=(anss[m]*fac[n])%mod;

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

[SDOI2008]沙拉公主的困惑线性筛_欧拉函数_逆元_快速幂

最新文章

热门文章

巴特西

[SDOI2008]沙拉公主的困惑 线性筛_欧拉函数_逆元_快速幂

最新文章

热门文章

[SDOI2008]沙拉公主的困惑线性筛_欧拉函数_逆元_快速幂