首页 > 代码库 > bzoj4891: [Tjoi2017]龙舟
bzoj4891: [Tjoi2017]龙舟
求$\frac{b_1b_2b_3...b_m}{a_1a_2a_3...a_m}\%M$
M<=1e18,m<=100000,数据组数<=50
用pollard-rho分解M的质因数,提取出$b_i,a_i$与M不互质的部分处理一下
#include<cstdio>#include<algorithm>typedef long long i64;typedef long double ld;char buf[65536],*ptr=buf+65536;int G(){ if(buf+65536==ptr)fread(ptr=buf,1,65536,stdin); return *ptr++;}i64 _(){ i64 x=0; if(ptr-buf<65000){ while(*ptr<48)++ptr; while(*ptr>47)x=x*10+(*ptr++)-48; }else{ int c=G(); while(c<48)c=G(); while(c>47)x=x*10+c-48,c=G(); } return x;}int n,m,k;i64 b[100007],a[22][100007];int fp,ts[100];i64 fs[100];i64 mul(i64 a,i64 b,i64 c){ if(c<=2000000000ll)return a*b%c; i64 r=a*b-i64(ld(a)/c*b)*c; if(r>=c||r<=-c)r%=c; return r>=0?r:r+c;}i64 pw(i64 a,i64 n,i64 P){ i64 v=1; for(;n;n>>=1,a=mul(a,a,P))if(n&1)v=mul(v,a,P); return v;}i64 gcd(i64 a,i64 b){ if(a<0)a=-a; for(i64 c;b;c=a,a=b,b=c%b); return a;}bool mr(i64 n){ i64 z=n-1; int t=0; while(~z&1)z>>=1,++t; for(int i=0;i<15;++i){ i64 a=rand()%(n-1)+1; i64 x=pw(a,z,n); for(int j=0;j<t;++j){ i64 y=mul(x,x,n); if(y==1&&x!=1&&x!=n-1)return 0; x=y; } if(x!=1)return 0; } return 1;}i64 get(i64 x,int c){ int i=1,j=2; i64 a=(rand()^i64(rand())<<31)%(x-1)+1,b=a; while(1){ a=mul(a,a,x); if((a+=c)>=x)a%=x; i64 p=gcd(a-b,x); if(p!=1)return p; if((++i)==j)j<<=1,b=a; }}void calc(i64 n){ if(n==1)return; if(mr(n)){ fs[fp++]=n; return; } for(int c=12347;;++c){ i64 a=get(n,c); if(a!=n){ i64 b=gcd(a,n/a); calc(a/b); calc(n/a/b); calc(b); return; } }}i64 cal(i64*b,i64*a,i64 M){ fp=0; calc(M); std::sort(fs,fs+fp); fp=std::unique(fs,fs+fp)-fs; i64 phi_M=M; for(int i=0;i<fp;++i)ts[i]=0,phi_M=phi_M/fs[i]*(fs[i]-1); i64 B=1,A=1,x; for(int i=1;i<=m;++i){ x=b[i]; if(fs[0]==2)for(;~x&1;x>>=1,++ts[0]); for(int j=(fs[0]==2);j<fp;++j){ for(i64 p=fs[j],y=x/p;y*p==x;x=y,y=y/p,++ts[j]); } B=mul(B,x,M); } for(int i=1;i<=m;++i){ x=a[i]; if(fs[0]==2)for(;~x&1;x>>=1,--ts[0]); for(int j=(fs[0]==2);j<fp;++j){ for(i64 p=fs[j],y=x/p;y*p==x;x=y,y=y/p,--ts[j]); } A=mul(A,x,M); } B=mul(B,pw(A,phi_M-1,M),M); for(int i=0;i<fp;++i){ if(ts[i]<0)return -1; B=mul(B,pw(fs[i],ts[i],M),M); } return B;}int main(){ srand(77151); n=_();m=_();k=_(); for(int i=1;i<=m;++i)b[i]=_(); for(int t=1;t<=n;++t) for(int i=1;i<=m;++i)a[t][i]=_(); for(int i=0;i<k;++i){ int x=_(); i64 M=_(); printf("%lld\n",cal(b,a[x],M)); } return 0;}
bzoj4891: [Tjoi2017]龙舟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。