You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

bitset 高精度

. 2 min read
脑残了,用bitset写高精度x
#include <iostream>
#include <cstdio>
#include <cmath>
#include <bitset>
using namespace std;
typedef bitset<127> Bint;
bool operator<(const Bint &a,const Bint &b)
{
    for(int i=a.size()-1; ~i; --i)
        if(a[i]<b[i])return 1;
    return 0;
}
bool operator!=(const Bint &a,const Bint &b)
{
    for(int i=a.size()-1; ~i; --i)
        if(a[i]!=b[i])return 1;
    return 0;
}
Bint operator+(const Bint &a,const Bint &b)
{
    return b.any()?(a^b)+((a&b)<<1):a;
}
Bint& operator+=(Bint &a,const Bint &b)
{
    return a=a+b;
}
Bint operator-(const Bint &a)
{
    return Bint(1)+~a;
}
Bint& operator-=(Bint &a,const Bint &b)
{
    return a+=-b;
}
Bint operator-(Bint a,const Bint &b)
{
    return a-=b;
}
Bint operator*(Bint a,Bint b)
{
    Bint r(0);
    for(; b.any(); b>>=1,a+=a)if(b[0])r+=a;
    return r;
}
Bint& operator*=(Bint &a,const Bint &b)
{
    return a=a*b;
}
Bint operator%=(Bint &dividend,const Bint &divisor)
{
    if(dividend<divisor||divisor.none())return dividend;
    Bint c,res=0;
    for(int k; divisor<dividend;)
    {
        for(k=0,c=divisor; !(dividend<c); c<<=1,++k)
            if(dividend<divisor+c)
            {
                res+=1<<k;
                break;
            }
        if(dividend<divisor+c)break;
        res+=1<<(k-1);
        dividend-=c>>1;
    }
    return dividend;//res是商
}
Bint operator/(Bint dividend,const Bint &divisor)
{
    if(dividend<divisor||divisor.none())return dividend;
    Bint c,res=0;
    for(int k; divisor<dividend;)
    {
        for(k=0,c=divisor; !(dividend<c); c<<=1,++k)
            if(dividend<divisor+c)
            {
                res+=1<<k;
                break;
            }
        if(dividend<divisor+c)break;
        res+=1<<(k-1);
        dividend-=c>>1;
    }
    return res;
}
istream& getb(istream &is,Bint &val)
{
    int sign=1,ch=is.get();
    for(; !isdigit(ch)&&ch!=EOF; ch=is.get())
        if(ch=='-')
            sign=-sign;
    for(val=0; isdigit(ch); ch=is.get())
        val=(val<<3)+(val<<1)+(ch^'0');
    if(sign==-1)val=-val;
    return is.putback(ch);
}
ostream& putb(ostream &os,const Bint &val)
{
    if(Bint(9)<val)putb(os,val/10);
    return os.put(val.to_ulong()%10+'0');
}

Bint gcd(Bint m,Bint n){
	if (m==n) return m;
	if (m<n) return gcd(n,m);
	if (m[0]==1)
		return (n[0]==1)?gcd(m>>1,n>>1)<<1:gcd(m>>1,n);
	return (n[0]==1)?gcd(m,n>>1):gcd(n,m-n);
}
Bint a,b;
int main(){
	cin>>a>>b;
	cout<<gcd(a,b)<<endl;
	return 0;
}


本站总访问量 正在加载今日诗词....