BZOJ-1128 [POI2008]Lam
从后往前考虑。
然后这题就变成了高精模版题
之所以没什么人写是因为要写高精gcd
考虑当前为x/y,x,y均为Bigint
接下来要变成x/(y*p)
那么x和p需要除去它们的gcd
然而gcd(x,p)=gcd(x%p,p)
所以只要写一个高精模单精就好了= =
/************************************************************** Problem: 1128 User: wjy1998 Language: C++ Result: Accepted Time:468 ms Memory:10956 kb ****************************************************************/ #include<cstdio> #define mod 1000000000 char buf[1<<14],*O=buf,s[11],t;int n,p[1010],g; void pri(int x){ if(!x)*O++='0';else{ for(t=0;x;x/=10)s[++t]=x%10+'0'; for(;t;*O++=s[t--]); } } void pr9(int x){ for(int i=1;i<=9;i++)s[i]=x%10+'0',x/=10; for(int i=9;i;*O++=s[i--]); } int gcd(int x,int y){return!y?x:gcd(y,x%y);} class B{public: int len;long long s[640]; B&operator*=(int x){ for(int i=1;i<=len;i++)s[i]*=x; for(int i=1;i<=len;i++)if(s[i]>=mod)s[i+1]+=s[i]/mod,s[i]%=mod; for(;s[len+1];len++); } B&operator/=(int x){ s[0]=0; for(int i=len;i;i--)s[i-1]+=(s[i]%x)*mod,s[i]/=x; while(len>1&&!s[len])len--; } void pr(){ pri(s[len]); for(int i=len-1;i;pr9(s[i--])); } }ans[1010][2],x,y,one,zero; int operator%(const B&a,int x){ int f=0; for(int i=a.len;i;i--)f=(1LL*f*mod+a.s[i])%x; return f; } int main(){ scanf("%d",&n);zero.len=one.len=one.s[1]=1;x=y=one; for(int i=1;i<=n;i++)scanf("%d",p+i); for(int i=n;i;i--){ g=gcd(p[i],x%p[i]),x/=g,y*=p[i]/g,ans[i][0]=x,ans[i][1]=y; if(p[i]==1){ for(;--i;ans[i][0]=zero,ans[i][1]=one);break; } else g=gcd(p[i]-1,y%(p[i]-1)),x*=(p[i]-1)/g,y/=g; } for(int i=1;i<=n;i++)ans[i][0].pr(),*O++='/',ans[i][1].pr(),*O++=0,puts(buf),O=buf; }