bzoj1876: [SDOI2009]SuperGCD

2019-11-06 06:17:49

字体：大中小

来源：转载

供稿：网友

传送门哈，不用高精度的做法应该都会吧、可是要高精度。于是我们可以将A%B化为A-B^x-…… x为2的幂次。这样用辗转相除法求出gcd

#include<cstring> #include<cmath> #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm>#define ll long long#define mo 1000000000using namespace std;struct bignum{ ll a[1200]; bool Operator <= (bignum x){ if (a[0]!=x.a[0]) return a[0]<x.a[0]; for (int i=a[0];i>=1;i--) if (a[i]!=x.a[i]) return a[i]<x.a[i]; return 1; } void operator *= (ll x){ for (int i=1;i<=a[0];i++) a[i]*=x; for (int i=1;i<=a[0];i++){ a[i+1]+=a[i]/mo; a[i]%=mo; } if (a[a[0]+1]) a[0]++; } void operator /= (ll x){ ll y=0; for (int i=a[0];i>=1;i--){ y=y*mo+a[i]; a[i]=y/x; y%=x; } if (!a[a[0]]) a[0]--; } void operator -= (bignum x){ for (int i=1;i<=a[0];i++) a[i]-=x.a[i]; for (int i=1;i<=a[0];i++) if (a[i]<0) a[i]+=mo,a[i+1]--; while (!a[a[0]]&&a[0]) a[0]--; } void yw(char *b){ ll x=0; int len=strlen(b); for (int i=len;i>0;i--){ if (i%9==0){a[i/9+1]=x; x=0;} x=x*10+b[len-i]-48; } a[1]=x; a[0]=(len-1)/9+1; } void PRint(){ printf("%d",a[a[0]]); for (int i=a[0]-1;i>=1;i--) printf("%09d",a[i]); printf("/n"); }}c,d;int j=0;char a[10005],b[10005];int main(){ scanf("%s%s",&a,&b); c.yw(a); d.yw(b); if (c<=d) swap(c,d); while (d.a[0]!=0){ while (!(d.a[1]&1)&&!(c.a[1]&1)) d/=2,c/=2,j++; while (!(d.a[1]&1)) d/=2; while (!(c.a[1]&1)) c/=2; if (c<=d) swap(c,d); c-=d; if (c<=d) swap(c,d); } for (;j>0;j--) c*=2; c.print(); return 0;}

上一篇：yii2中getter 和 setter 注意事项

下一篇：leetcode_404. Sum of Left Leaves