高精度取模模板

冷不防 2023-10-10 10:24 56阅读 0赞

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    #define ll long long
    int turn[105];
    struct node{
        int num[105];
        friend bool operator <(node a,node b){
            if(a.num[0]^b.num[0])  return a.num[0]<b.num[0];
            for(register int i=a.num[0];i;--i)  if(a.num[i]^b.num[i])  return a.num[i]<b.num[i];
            return 1;
        }
        friend node operator -(node a,node b){
            int pos;
            for(register int i=1;i<=a.num[0];++i){
                if(a.num[i]<b.num[i])  a.num[i]+=10,--a.num[i+1];
                a.num[i]-=b.num[i];
            }
            while(a.num[0]&&!a.num[ a.num[0] ]) --a.num[0];
            return a;
        }
        friend node operator %(node a,node b){
            int cnt=a.num[0]-b.num[0]+1;
            node res;
            for(register int i=cnt;i;--i){
                memset(res.num,0,sizeof(res.num));
                for(register int j=1;j<=b.num[0];++j)  res.num[j+i-1]=b.num[j];
                res.num[0]=b.num[0]+i-1;
                while(res<a) a=a-res;
            }
            return a;
        }
    }n,m;
    inline void read(node &n)
    {
        int num=0; char ch=getchar();
        while(ch<'0'||ch>'9')  ch=getchar();
        while(ch>='0'&&ch<='9')  turn[++num]=(ch^48),ch=getchar();
        n.num[0]=num;
        for(register int i=1;i<=num;++i)  n.num[i]=turn[num-i+1];
    }
    void gcd(node a,node b){
        //cout<<a.num[0]<<' '<<b.num[0]<<' '<<b.num[1]<<"#"<<endl;
        if(!b.num[0]){
            if(a.num[0]==1&&a.num[1]==1){ cout<<"Yes"<<endl; return; }
            else { cout<<"No"<<endl; return ; }
        }
        if(a<b)  gcd(a,b%a);
        else gcd(b,a%b);
    }
    int main()
    {    
        int t;
        scanf("%d",&t);
        while(t--){
            read(n),read(m);
            //n=n%m;
            //for(register int i=n.num[0];i;--i) cout<<n.num[i];
            gcd(n,m);
        }
    }

转载于:https://www.cnblogs.com/three-D/p/11479919.html