【GDOI 2011 DAY2 T3】零什么的最讨厌了 （快速求阶乘、中国剩余定理）

问题描述：

林记在做数学习题的时候，经常遇到这种情况：苦思冥想了很久终于把问题解出来，结果发现答案是0，久而久之林记在得到习题答案是0的时候就没有了做出一道难题的成就感。于是林记决定：以后出题，答案一定不能是0，例如求n！最低位非零数这样的习题就很不错了。

现在林记提出了一个更难一点的问题：求n！在K进制下的最低位非零数。其中K符合一些特殊的条件：K是由若干个互不相同的质数相乘得出来的，例如K=2,3,5,6,7,10……

输入格式：

首先输入的第一行是一个整数Q，表示询问的个数。

接下来是Q个询问，每个询问有两行组成，第一行首先是一个整数nk，然后紧跟着nk个正整数：m1，m2,……m_nk，则K为所有mi的乘积，输入保证mi是有若干个互不相同的质数相乘得出来的。接下来一行给出一个整数n。

输出格式：

对于每个询问，如果K不符合题目限制，则输出“I hate zero.”（不用加双引号）。否则输出K进制下n！的最低位非零数。

输入样例：	输出样例：
3 1 17 9 1 6 49 1 93 16	15 2 78

数据范围：

对于10%的数据满足：n≤10，K≤100

对于50%的数据满足：n≤100000，K≤100

对于100%的数据满足：n≤10¹⁵，K≤10¹⁵，mi≤10⁶，Q≤20

【分析】

　　快速求阶乘大法！！

　　下面某步还用到 威尔逊定理 （p-1）！%p=p-1...... （也可以预处理出来的）

　　把m分解质因数，对于质数p单独求n！=p^a+b的a的值和b%p的值（logn递归搞定），然后用中国剩余定理合并起来。

　　

　　long long的乘积会爆，所以...要用那个不断乘2的方法：

　　

LL mul(LL x,LL y,LL p)

{

	if(x==0||y==0) return 0;

	LL now=x,yy=y,add=0;

	while(yy>1)

	{

		if(yy%2!=0) add=(add+now)%p;

		now=(now*2)%p;

		yy/=2;

	}

	return (now+add)%p;

}

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 1000010

 #define INF 0xfffffff

 #define LL long long

 LL nk,m[Maxn],ml,K;

 LL n;

 LL prime[Maxn],pl;

 bool q[Maxn];

 LL mn;

 LL mymin(LL x,LL y) {return x<y?x:y;}

 void get_pri(LL mx)

 {

     pl=;

     memset(q,,sizeof(q));

     for(LL i=;i<=mx;i++)

     {

         if(q[i]) prime[++pl]=i;

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

         {

             if(i*prime[j]>mx) break;

             q[i*prime[j]]=;

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

         }

     }

 }

 bool div(LL mm)

 {

     for(LL i=;prime[i]*prime[i]<=mm;i++) if(mm%prime[i]==)

     {

         m[++ml]=prime[i];

         mm/=prime[i];

         while(mm%prime[i]==) return ;

     }

     if(mm!=) m[++ml]=mm;

     return ;

 }

 bool init()

 {

     ml=;

     scanf("%lld",&nk);

     K=;

     bool ok=;

     for(int i=;i<=nk;i++)

     {

         LL mm;

         scanf("%lld",&mm);K*=mm;

         if(!div(mm)) ok=;

     }

     sort(m+,m++ml);

     for(LL i=;i<=ml;i++) if(m[i]==m[i-]) {ok=;break;}

     scanf("%lld",&n);

     if(!ok) return ;

     return ;

 }

 LL f[Maxn];

 struct node{LL x,y;};

 node c[Maxn];

 node ffind(LL x,LL p)

 {

     node ans;

     if(x<p)

     {

         ans.x=;

         ans.y=f[x];

         return ans;

     }

     ans.x=;ans.y=;

     node t=ffind(x/p,p);

     ans.x+=t.x; ans.y*=t.y;

     ans.y=(ans.y*f[x%p])%p;

     ans.x+=x/p;

     LL y=(((x/p)%)==)?:p-;

     ans.y=(ans.y*y)%p;

     return ans;

 }

 LL mul(LL x,LL y,LL p)

 {

     if(x==||y==) return ;

     LL now=x,yy=y,add=;

     while(yy>)

     {

         if(yy%!=) add=(add+now)%p;

         now=(now*)%p;

         yy/=;

     }

     return (now+add)%p;

 }

 LL qpow(LL x,LL b,LL p)

 {

     LL ans=;

     while(b)

     {

         if(b&) ans=mul(ans,x,p);

         x=mul(x,x,p);

         b>>=;

     }

     return ans;

 }

 LL d[Maxn];

 LL get_ans()

 {

     mn=c[].x;

     for(LL i=;i<=ml;i++) mn=mymin(mn,c[i].x);

     for(LL i=;i<=ml;i++)

     {

         if(c[i].x>mn) {d[i]=;continue;}

         LL bm=qpow(K/m[i],mn,m[i]);

         bm=qpow(bm,m[i]-,m[i]);

         d[i]=mul(bm,c[i].y,m[i]);//(bm*c[i].y)%m[i];

     }

     LL ans=;

     for(LL i=;i<=ml;i++)

     {

         LL y=qpow(K/m[i],m[i]-,m[i]);

         //ans=(ans+((K/m[i]*y)%K)*d[i])%K;

         ans=(ans+mul(mul(K/m[i],y,K),d[i],K))%K;

     }

     return ans;

 }

 int main()

 {

     get_pri();

     int T;

     scanf("%d",&T);

     while(T--)

     {

         if(!init()) {printf("I hate zero.\n");continue;}

         for(LL i=;i<=ml;i++)

         {

             f[]=;

             for(LL j=;j<m[i];j++) f[j]=(f[j-]*j)%m[i];

             c[i]=ffind(n,(LL)m[i]);

         }

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

     }

     return ;

 }

2016-09-04 19:37:26

【GDOI 2011 DAY2 T3】零什么的最讨厌了 （快速求阶乘、中国剩余定理）的相关教程结束。