BZOJ-1128 [POI2008]Lam

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

从后往前考虑。

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

之所以没什么人写是因为要写高精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
boardmodelpaper.com 说:
2024年1月19日 23:42

Board Model Papers 2024 Download with Suggestions for 10th Class Textbooks 2024 Pdf Download and SSLC New Syllabus Sample Question Paper 2024 and different types of model papers boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course Languages & Subjects Important Question for the above link.


登录 *


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