问题描述：
林记在做数学习题的时候，经常遇到这种情况：苦思冥想了很久终于把问题解出来，结果发现答案是0，久而久之林记在得到习题答案是0的时候就没有了做出一道难题的成就感。于是林记决定：以后出题，答案一定不能是0，例如求n！最低位非零数这样的习题就很不错了。
现在林记提出了一个更难一点的问题：求n！在K进制下的最低位非零数。其中K符合一些特殊的条件：K是由若干个互不相同的质数相乘得出来的，例如K=2,3,5,6,7,10……
输入格式：
首先输入的第一行是一个整数Q，表示询问的个数。
接下来是Q个询问，每个询问有两行组成，第一行首先是一个整数nk，然后紧跟着nk个正整数：m1，m2,……mnk，则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≤1015，K≤1015，mi≤106，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