【BZOJ 2186】 2186: [Sdoi2008]沙拉公主的困惑 （欧拉筛，线性求逆元）

【分析】

　　本来做这题是找信心，然而。。

　　首先我们知道 如果x与y互质，那么x+y与y也互质。

　　所以只需要求$\phi(m!)* \dfrac{n!}{m!} $

　　问题转换成求$\phi(m!)$

　　我们知道一种求法，就是把$m！$分解质因数，对于每个素数乘上一个$\dfrac{p-1}{p}$

　　显然<=m的素数就是$m！$的分解质因数。

　　中间要用到的线性求逆元：

　　ny[1]=1;

　　for(int i=2;i<=Maxn-10;i++) ny[i]=(R-R/i*ny[R%i])%R;

　　

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 10000010

 #define LL long long

 int R;

 int mul(int x,int y)

 {

     LL K1=(LL)x,K2=(LL)y;

     K1=(K1*K2)%R;

     return (int)K1;

 }

 int pri[Maxn],pl;

 int ny[Maxn];

 bool vis[Maxn];

 void init()

 {

     for(int i=;i<=Maxn-;i++)

     {

         if(!vis[i]) pri[++pl]=i;

         for(int j=;j<=pl;j++)

         {

             LL K1=(LL)i,K2=(LL)pri[j];

             K1=K1*K2;

             if(K1>Maxn) break;

             vis[K1]=;

             if(i%pri[j]==) break;

         }

     }

 }

 int A[Maxn],B[Maxn];

 void get_ans()

 {

     A[]=;

     for(int i=;i<=Maxn-;i++)

     {

         A[i]=mul(A[i-],i);

     }

     int now=;

     B[]=;

     for(int i=;i<=Maxn-;i++)

     {

         B[i]=B[i-];

         while(pri[now]<=i&&now<=pl)

         {

             B[i]=mul(mul(pri[now]-,ny[pri[now]]),B[i]);

             // B[i]=((B[i]*(pri[now]-1)%R)%R)*ny[pri[now]];

             // B[i]%=R;

             now++;

             if(now==pl) break;

         }

     }

 }

 int main()

 {

     int T;

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

     // memset(vis,0,sizeof(vis));

     for(int i=;i<=Maxn-;i++) vis[i]=;

     init();

     ny[]=;

     for(int i=;i<=Maxn-;i++) ny[i]=mul(R-R/i,ny[R%i]);

     get_ans();

     while(T--)

     {

         int n,m;

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

         int ans=mul(A[n],B[m]);

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

     }

     return ;

 }

这道恶心题又卡空间 又卡时间。

2017-02-13 13:48:22