BZOJ-1128 [POI2008]Lam

n+e posted @ 2015年6月30日 22:43 in BZOJ with tags 高精度 , 1405 阅读

从后往前考虑。

然后这题就变成了高精模版题

之所以没什么人写是因为要写高精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;
}
---By n+e

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter