更相减损术+高精度板子

压位1000ms

注意对偶数优化,一奇一偶可以÷2

两个偶数同时÷2再乘回去可以优化减法次数

/************************
    Problem: 1876
    User: Insider
    Language: C++
    Result: Accepted
    Time:1104 ms
    Memory:1300 kb
*************************/
 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iterator>
#include<string>
using namespace std;
 
struct BNUM
{
    int seq[2010],len;
     
    BNUM() { memset(seq,0,sizeof(seq)); len=0; }
     
    //I&O
    void readstr()
    {
        register char ch=0; int str[10010]={0};
        while (ch<'0' || ch>'9') ch=getchar();
        while (ch>='0' && ch<='9') { len++; str[len]=ch-'0'; ch=getchar(); }
        int pos=len,cache1; len=0;
        while (pos>=8)
        {
            cache1=0;
            for (int i=7;i>=0;i--) cache1=cache1*10+str[pos-i];
            len++; seq[2000-len+1]=cache1;
            pos-=8;
        }
        if (!pos) return; cache1=0;
        for (int i=1;i<=pos;i++) cache1=cache1*10+str[i];
        len++; seq[2000-len+1]=cache1;
    }
    void output()
    {
        if (!len) { putchar('0'); putchar('\n'); return; }
        int pos=2000-len+1; while (!seq[pos]) pos++;
        printf("%d",seq[pos]); pos++;
        for (;pos<=2000;pos++) printf("%08d",seq[pos]); putchar('\n');
    }
     
    //opetrtor
    BNUM operator = (BNUM b) { len=b.len; memcpy(seq,b.seq,sizeof(seq)); return *this; }
    bool operator < (BNUM &b)
    {
        if (len<b.len) return true;
        if (len>b.len) return false;
        for (int i=2000-len+1;i<=2000;i++)
        {
            if (seq[i]<b.seq[i]) return true;
            else if (seq[i]>b.seq[i]) return false;
        }
    }
    bool operator == (BNUM &b)
    {
        if (len!=b.len) return false;
        for (int i=2000-len+1;i<=2000;i++) if (seq[i]!=b.seq[i]) return false;
        return true;
    }
     
    //calculations
    BNUM operator - (BNUM& b)
    {
        BNUM c;
        for (int i=2000;i>=2000-len+1;i--)
        {
            if (seq[i]<b.seq[i]) { seq[i]+=100000000; seq[i-1]--; }
            c.seq[i]=seq[i]-b.seq[i];
        }
        c.len=len; while (!c.seq[2000-c.len+1]) c.len--;
        return c;
    }
     
    void make1()
    {
        register int num=0;
        for (int i=2000-len+1;i<=2000;i++)
        {
            num*=100000000; num+=seq[i];
            if (num>=2) { seq[i]=num/2; num=num%2; }
            else seq[i]=0;
        }
        if (!seq[2000-len+1]) len--;
    }
    void make2()
    {
        int chx[2010]={0};
        for (int i=2000;i>=2000-len+1;i--)
        {
            chx[i]+=seq[i]*2;
            if (chx[i]>100000000) { chx[i-1]+=1; chx[i]-=100000000; }
        }
        memcpy(seq,chx,sizeof(chx));
        len++; if (!seq[2000-len+1]) len--;
    }
     
};
 
int main()
{
    BNUM a,b; int mark=0;
    a.readstr(); b.readstr();
     
    while (!(a==b))
    {
        while ((!(a.seq[2000]%2)) && (!(b.seq[2000]%2)))
        {
            mark++;
            a.make1(); b.make1();
        }
        while (!(a.seq[2000]%2)) a.make1();
        while (!(b.seq[2000]%2)) b.make1();
        if (a==b) break;
        if (a<b) b=b-a;
        else a=a-b;
    }
    while (mark) { mark--; a.make2(); }
    a.output();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.