题解

167 条题解

  • 4
    @ 2019-08-01 20:57:35

    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int L=10005;
    string mul(string a,string b)
    {
    string s;
    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();
    fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
    for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
    for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
    for(int i=1;i<=La;i++)
    for(int j=1;j<=Lb;j++)
    nc[i+j-1]+=na[i]*nb[j];
    for(int i=1;i<=La+Lb;i++)
    nc[i+1]+=nc[i]/10,nc[i]%=10;
    if(nc[La+Lb]) s+=nc[La+Lb]+'0';
    for(int i=La+Lb-1;i>=1;i--)
    s+=nc[i]+'0';
    return s;
    }
    int sub(int *a,int *b,int La,int Lb)
    {
    if(La<Lb) return -1;//如果a小于b,则返回-1
    if(La==Lb)
    {
    for(int i=La-1;i>=0;i--)
    if(a[i]>b[i]) break;
    else if(a[i]<b[i]) return -1;//如果a小于b,则返回-1
    }
    for(int i=0;i<La;i++)//高精度减法
    {
    a[i]-=b[i];
    if(a[i]<0) a[i]+=10,a[i+1]--;
    }
    for(int i=La-1;i>=0;i--)
    if(a[i]) return i+1;//返回差的位数
    return 0;//返回差的位数
    }
    string div(string n1,string n2,int nn)
    {
    string s,v;//s存商,v存余数
    int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;
    fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);//数组元素都置为0
    for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';
    for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';
    if(La<Lb || (La==Lb && n1<n2)) {cout<<0<<endl;return n1;}
    int t=La-Lb;//除被数和除数的位数之差
    for(int i=La-1;i>=0;i--)//将除数扩大10^t倍
    if(i>=t) b[i]=b[i-t];
    else b[i]=0;
    Lb=La;
    for(int j=0;j<=t;j++)
    {
    int temp;
    while((temp=sub(a,b+j,La,Lb-j))>=0)
    {
    La=temp;
    r[t-j]++;
    }
    }
    for(i=0;i<L-10;i++)
    r[i+1]+=r[i]/10,r[i]%=10;//统一处理进位
    while(!r[i]) i--;//将整形数组表示的商转化成字符串表示的
    while(i>=0) s+=r[i--]+'0'; //cout<<s<<endl;
    i=tp;
    while(!a[i]) i--;
    while(i>=0) v+=a[i--]+'0';
    if(v.empty()) v="0";
    if(nn==1) return s;
    if(nn==2) return v;
    }
    bool judge(string s)//判断s是否为全0串
    {
    for(int i=0;i<s.size();i++)
    if(s[i]!='0') return false;
    return true;
    }
    string gcd(string a,string b)//求最大公约数
    {
    string t;
    while(!judge(b))//如果余数不为0,继续除
    {
    t=a;//保存被除数的值
    a=b;//用除数替换被除数
    b=div(t,b,2);//用余数替换除数
    }
    return a;
    }
    int main()
    {
    string a,b;
    while(cin>>a>>b)
    {
    if(a.size()<b.size() || (a.size()==b.size() && a<b))
    {
    swap(a,b);
    }
    cout<<div(mul(a,b),gcd(a,b),1)<<endl;//求最小公倍数
    }
    return 0;
    }

  • 1
    @ 2022-06-15 09:27:36

    #include <iostream>
    using namespace std;
    int main(){
    long long a,b;
    cin>>a>>b;
    if(a+1==b||b+1==a){
    cout<<a*b;
    return 0;
    }
    if(b%a==0){
    cout<<b;
    return 0;
    }
    if(a%b==0){
    cout<<a;
    return 0;
    }
    long long k;
    if(a>b)k=a;
    if(b>a)k=b;
    else {
    for(long long i=k;i<=a*b;i++){
    if(i%a==0&&i%b==0){
    cout<<i;
    return 0;
    }
    }
    }
    cout<<a*b;
    return 0;
    }

  • 1
    @ 2021-10-17 20:33:15
    import math;print(math.gcd(int(input()),int(input())))
    
  • 1
    @ 2019-06-14 09:40:03
    import java.util.*;
    import java.math.*;
    
    public class Main
    {
        public static void main(String []args)
        {
            Scanner sc = new Scanner(System.in);
            BigInteger a = sc.nextBigInteger();
            BigInteger b = sc.nextBigInteger();
            System.out.print(a.divide(gcd(a, b)).multiply(b));
        }
        public static BigInteger gcd(BigInteger a, BigInteger b)
        {
            if (b.compareTo(new BigInteger("0")) == 0)
            {
                return a;
            }
            else
            {
                return gcd(b, a.mod(b));
            }
        }
    }
    
    
  • 1
    @ 2018-10-17 20:36:58
    def gcd(m,n):
        while m>0:
            c = n % m
            n = m
            m = c
        return n
    x,y=map(int,input().split())  
    c=x*y//gcd(x,y)
    print(c)
    
  • 1
    @ 2009-10-14 17:43:14

    第一遍求最大公约数的时候用的递归,结果堆栈溢出了。。改非递归就秒杀了~

    只用到了高精度减。乘。除就可以了。。

    http://hi.baidu.com/%C4%BE%D7%D3%C8%D5%D4%C8/blog/item/ac958ad8a44457e339012fdd.html

    • @ 2021-02-20 05:03:54

      赞,之前被RE淹没,总算搞定了

  • 0
    @ 2021-02-20 04:40:23

    AWSL,Python保平安QAQ

    个人做法就是,写一个近乎功能完整的BigInt类,重载operator来实现和int相似的交互逻辑,然后根据lcm(a, b) = a * b / gcd(a, b),写个辗转相除法,差不多了。当然这样实现真的很难调试,估计实际上很多地方也没必要专门写,可能浪费了不少行数。

    减法的做法较为直观,从高位到低位依次减,注意有时候如果不够减高位需要退1,高位也可能不够减,所以要用while往高位退到够用了为止;通过提前对比大小规避小减大出负数。是不是有回到了小学的感觉呢~

    除法的原理还是有点意思的,实际上就是做减法,先补位到和被除数同样长度然后减到不能减为止,重复这个操作(补位要-1!),这就相当于做了我们平常的手算除法。

    小技巧
    才意识到如果在struct为一个数据类d型写了constructor,传递变量时如果需要的类型是那个struct就可以直接传入d类的数据,会自动调用constructor创建一个新的关于d的struct。
    例如如果我要return BigInt(3),实际只用写return 3,编译会自动调用BigInt(3),把int变成BigInt。

    下面是究极无敌脑瘫采坑实录,带(?)都是改bug中间遇到的貌似是bug,不过修了也没什么变化的东西
    1. 数据上限不是答案上限,答案最大能到10^200次方,可别把MAXN开小了!
    2. (?)对于这样的一个存储了数组指针的BigInt类,如果仅是用=赋值,会出现 shallow copy 的问题,直接将老struct中的指针拷贝到新struct里,而不会复制一份数组内容。保险的操作就是 重载operator= ,自定义拷贝操作,全部做copy by value.
    3. 0一定要明确规范定义,否则定义operator==时可能会出现两个来路不同的0不相等的问题。例如刚开始我的BigInt(int x) constructor就没有定义特殊行为,导致这里的0被表示为l = 0, dg为空。我的做法就是每次可能涉及0,都确保0是同样的定义:l = 1; dg[1] = 0.
    4. 能避免负数就 避免负数 ,呃。。。反正我是直接逃了。凡是能写 a > b的时候,一定不要写a - b > 0; 减法遇到负数能烦死。
    5. 减法和除法因为要操作原数字,要记得新赋值给一个被减数和被除数,结果我好家伙,把减法里while那段写了个没有赋值过的res。。。。。
    6. 究极神秘bug,求大佬解释!!! (166) while (num >= x.exp(diff) * cnt) cnt++; 本来我写的是while (num >= x.exp(diff) * ++cnt); 但是发现这样写的时候++cnt在cnt = 1不成立的时候就没有实际加进去下一行打出来的cnt == 0,按我的理解就算不成立不也应该保留cnt += 1吗?这真的把我搞死了。
    7. 位数维护一定要做好,每次做完一个算术操作一定要记得更新答案的位数。
    8. 不要用递归!!因为某些神秘原因,至少这个编译器 没有尾递归优化 ,有人说-O2就会有,有人说ANSI并没有规定这个编译器优化,众说纷纭。但是注意到递归存struct比较大,如果没有优化,就会有一大堆的长数组被卡在栈里,于是就爆栈了;这就是Runtime Error(RE)的原因。因此 必须要写成递推形式 。还得感谢木子日匀大佬十一年前的评论。。。

    不说了,我先去自闭了。。。。。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    const int MAXN = 300;
    
    struct BigInt {
        int dg[MAXN], l;
    
        // Constructors
        BigInt() {
            memset(dg, 0, sizeof dg);
            dg[1] = 0; l = 1;
        }
    
        BigInt(int x) {
            if (!x) {
                dg[l = 1] = 0;
                return;
            }
            l = 0;
            memset(dg, 0, sizeof dg);
            while (x) {
                dg[++l] = x % 10;
                x /= 10;
            }
        }
    
        BigInt(string str) {
            memset(dg, 0, sizeof dg);
            l = str.length();
            for (int i = 0; i < l; i++) {
                dg[l - i] = str[i] - '0';
            }
        }
        // Auxiliary functions
    
        void gen_from_str(string str) {
            memset(dg, 0, sizeof dg);
            l = str.length();
            for (int i = 0; i < l; i++) {
                dg[l - i] = str[i] - '0';
            }
        }
    
        BigInt& operator=(BigInt x) {
            l = x.l;
            for (int i = 1; i <= l; i++) {
                dg[i] = x[i];
            }
            return *this;
        }
    
        void update_length() {
            while (!dg[l] && l > 1) l--; 
        }
    
        BigInt exp(int x) {     // This is only safe with x >= 0.
            BigInt res; 
            res.l = x + l;
            for (int i = l; i >= 1; i--) {
                res[i + x] = dg[i];
            }
            return res;
        }
    
        // Operators
        int& operator[] (int index) {
            return dg[index];
        }
    
        BigInt operator+ (BigInt x) {
            BigInt res;
            res.l = max(x.l, this -> l);
            for (int i = 1; i <= res.l; i++) {
                res[i] += x[i] + dg[i];
                res[i + 1] += res[i] / 10;
                res[i] %= 10;
            }
            res.l = (res[res.l + 1] ? res.l + 1 : res.l);
            return res;
        }
    
        BigInt operator- (BigInt x) { // The operation is not safe and assumes (*this >= x).
            BigInt res;
            res = *this;
            for (int i = x.l; i >= 1; i--) {
                res[i] -= x[i];
                int update_p = i;
    //            res.test();
                while (res[update_p] < 0) { 
                    res[update_p++] += 10;
                    res[update_p]--;
    //                res.test();
                }
            }
            res.l = l;
            res.update_length();       
            return res;
        }
    
        BigInt operator* (BigInt x) {
            BigInt res;
            for (int i = 1; i <= x.l; i++) {
                for (int j = 1; j <= this -> l; j++) {
                    res[i + j - 1] += x[i] * dg[j];
                    res[i + j] += res[i + j - 1] / 10;
                    res[i + j - 1] %= 10;
                }
            }
            int nl = x.l + (this -> l);
            res.l = (res[nl] ? nl : (nl - 1));
            return res;
        }
    
        BigInt operator* (int x) {
            BigInt res;
            for (int i = 1; i <= l; i++) {
                res[i] += dg[i] * x;
                res[i + 1] += res[i] / 10;
                res[i] %= 10;
            }
            res.l = (res[l + 1] ? l + 1 : l); // Careful with this!
            while (res[res.l] / 10 > 0) {
                res[res.l + 1] = res[res.l] / 10;
                res[res.l++] %= 10;
            }
            
            return res;
        }
    
        bool operator>= (BigInt x) {
            if (l > x.l) return true;
            if (l < x.l) return false;
            for (int i = l; i >= 1; i--) {
                if (dg[i] > x[i]) return true;
                if (dg[i] < x[i]) return false;
            }
            return true;
        }
    
        bool operator== (BigInt x) {
            if (l != x.l) return false;
            for (int i = 1; i <= l; i++) {
                if (dg[i] != x[i]) return false;
            }
            return true;
        }
    
        bool operator< (BigInt x) {
            return (x >= *this) && !(*this == x);
        }
    
        BigInt operator/ (BigInt x) {
            BigInt res;
            BigInt num; // numerator
            num = *this;
            int diff = num.l - x.l;
            if (diff < 0) return 0;
            res.l = diff + 1;
            while (diff >= 0) {
                int cnt = 1;
                while (num >= x.exp(diff) * cnt) cnt++;
                num = num - (x.exp(diff) * (--cnt));
    //            num.test();
    //            (x.exp(diff) * (cnt)).test();
    //            cout << cnt << endl;
                res[(diff--) + 1] = cnt;
            }
            res.update_length();
            return res;
        }
    
        BigInt operator% (BigInt x) {
            return *this - x * ((*this) / x);
        }
    
        void out() {
            for (int i = l; i >= 1; i--) {
                printf("%d", dg[i]);
            }
            printf("\n");
        }
        
        void test() {
            cout << l << " ";
            for (int i = 20; i >= 1; i--) {
                printf("%d", dg[i]);
            }
            printf("\n");
        }
    } a, b;
    
    BigInt gcd(BigInt a, BigInt b) {
        BigInt c;
        while (1) {
    //        cout << "a" << " "; a.test();
    //        cout << "b" << " "; b.test();
            if (a < b) swap(a, b);
            if (b == 0) return a;
            c = b;
            b = a % b;
            a = c;
        }
    }
    
    int main() {
        string str_a, str_b;
        cin >> str_a >> str_b;
        a.gen_from_str(str_a);
        b.gen_from_str(str_b);
        (a * b / gcd(a, b)).out();
        return 0;
    }
    
    • @ 2021-02-20 05:57:25

      Accepted

      状态 耗时 内存占用

      #1 Accepted 1ms 220.0 KiB
      #2 Accepted 1ms 228.0 KiB
      #3 Accepted 1ms 228.0 KiB
      #4 Accepted 1ms 228.0 KiB
      #5 Accepted 1ms 220.0 KiB
      #6 Accepted 1ms 228.0 KiB
      #7 Accepted 1ms 228.0 KiB
      #8 Accepted 2ms 228.0 KiB
      #9 Accepted 2ms 228.0 KiB
      #10 Accepted 1ms 228.0 KiB

  • 0
    @ 2013-07-18 17:01:59

    var m,n,zxgbs:integer;
    function zdgys(a,b:integer):integer;
    var
    r:integer;
    begin
    while b<>0 do
    begin
    r:=a mod b;
    a:=b;
    b:=r;
    end;
    zdgys:=a;
    end;

    begin
    read(m,n);
    zxgbs:=trunc(m*n/zdgys(m,n));
    writeln(zxgbs);
    end.

  • 0
    @ 2012-09-16 11:27:38

    var a,b,c:integer;

    begin

    read(a,b);

    if a>b then c:=a else c:=b;

    while (c mod a0) or (c mod b0) do c:=c+1;

    write(C)

    end.

  • 0
    @ 2009-11-09 15:48:21

    type

    nt=array[1..2,1..101]of longint;

    var

    t,s:string;

    a,b:nt;

    i,j,l1,l2:longint;

    flag:boolean;

    procedure adda(var a:nt);

    var

    i:longint;

    begin

    for i:=l1 downto 1 do

    begin

    a[2,i]:=a[2,i]+a[1,i];

    a[2,i+1]:=a[2,i+1]+a[2,i] div 10;

    a[2,i]:=a[2,i] mod 10;

    end;

    if a[2,l1+1]>0 then inc(l1);

    end;

    procedure addb(var b:nt);

    var

    i:longint;

    begin

    for i:=l2 downto 1 do

    begin

    b[2,i]:=b[2,i]+b[1,i];

    b[2,i+1]:=b[2,i+1]+b[2,i] div 10;

    b[2,i]:=b[2,i] mod 10;

    end;

    if b[2,l2+1]>0 then inc(l2);

    end;

    procedure print;

    begin

    for i:=l1 downto 1 do

    write(a[2,i]);

    writeln;

    flag:=false;

    end;

    procedure getmin(var a,b:nt);

    begin

    if l1l2 then addb(b)

    else

    begin

    for i:=l1 downto 1 do

    if a[2,i]=b[2,i] then continue

    else

    if a[2,i]b[2][i] then

    begin

    addb(b);

    exit;

    end;

    print;

    end;

    end;

    begin

    flag:=true;

    readln(s);

    t:=copy(s,1,pos(' ',s)-1);

    l1:=length(t);

    for i:=1 to l1 do

    val(t[i],a[2,l1-i+1]);

    a[1]:=a[2];

    t:=copy(s,pos(' ',s)+1,length(s)-l1-1);

    l2:=length(t);

    for i:=1 to l2 do

    val(t[i],b[2,l2-i+1]);

    b[1]:=b[2];

    while flag do getmin(a,b);

    end.

    先膜拜下matrix67神牛。OTL。

    好,开始。

    他blog里面有篇求lcm的文章,觉得那方法很叼。于是就来做这题,

    参看 http://www.matrix67.com/blog/archives/554

    结果基本上都超时了。。

    我的程序,用a[1],b[1]来记录初始值,a[2]参与运算。

    就用的matrix67的思想(我说过一次了)。

    但是TLE了6个点。(我又说过了)。

    各位看下有什么优化的方法。

  • 0
    @ 2009-11-09 10:19:14

    const base=10;

    type arr=array[0..210] of longint;

    var a,b,d,g,w:arr;

    procedure getin;

    var i,j:longint; str:string;

    begin

    readln(str);

    j:=pos(' ',str);

    i:=j-1;

    fillchar(a,sizeof(a),0);

    while i>0 do

    begin

    a[0]:=a[0]+1;

    if i>1 then

    begin val(copy(str,i,1),a[a[0]]); i:=i-1 end

    else

    begin val(copy(str,1,i),a[a[0]]); break end;

    end;

    str:=copy(str,j+1,length(str)-j);

    i:=length(str);

    fillchar(b,sizeof(b),0);

    while i>0 do

    begin

    b[0]:=b[0]+1;

    if i>1 then

    begin val(copy(str,i,1),b[b[0]]); i:=i-1 end

    else

    begin val(copy(str,1,i),b[b[0]]); break end;

    end;

    end;

    function equal(a,b:arr):boolean;

    var i:longint;

    begin

    if a[0]b[0] then exit(false);

    for i:=1 to a[0] do

    if a[i]b[i] then exit(false);

    equal:=true;

    end;

    function bigger(a,b:arr):boolean;

    var i:longint;

    begin

    if a[0]>b[0] then exit(true);

    if a[0]0 then a[0]:=a[0]+1;

    end;

    procedure minus(var a,b:arr;dl:longint);

    var c:arr; i:longint;

    begin

    fillchar(c,sizeof(c),0);

    c[0]:=b[0]+dl;

    for i:=1 to b[0] do c:=b[i];

    for i:=1 to a[0] do

    begin

    a[i]:=a[i]-c[i];

    if a[i]0) and (a[a[0]]=0) do a[0]:=a[0]-1;

    end;

    procedure plus(var a:arr;dl:longint);

    var i:longint;

    begin

    a[dl+1]:=a[dl+1]+1;

    i:=dl+1;

    while a[i]>=base do

    begin

    a:=a+a[i] div base;

    a[i]:=a[i] mod base;

    i:=i+1;

    end;

    if i>a[0] then a[0]:=i;

    end;

    procedure mul(a,b:arr;var w:arr);

    var i,j:longint; c:arr;

    begin

    fillchar(c,sizeof(c),0);

    for i:=1 to a[0] do

    for j:=1 to b[0] do

    begin

    c:=c+a[i]*b[j];

    if c>=base then

    begin

    c:=c+c div base;

    c:=c mod base;

    end;

    end;

    i:=1;

    while i=base then

    begin

    c:=c+c[i] mod base;

    c[i]:=c[i] div base;

    end;

    i:=i+1;

    end;

    i:=201;

    while c[i]=0 do i:=i-1;

    c[0]:=i;

    w:=c;

    end;

    procedure gcd(a,b:arr);

    var i:longint;

    begin

    fillchar(g,sizeof(g),0);

    g[0]:=1; g[1]:=1;

    while not equal(a,b) do

    begin

    if not odd(a[1]) then

    if not odd(b[1]) then

    begin div2(a); div2(b); mul2(g) end

    else div2(a)

    else

    if not odd(b[1]) then div2(b)

    else if bigger(a,b) then minus(a,b,0) else minus(b,a,0);

    end;

    mul(g,a,g);

    end;

    function larger(a,b:arr;dl:longint):boolean;

    var c:arr; i:longint;

    begin

    fillchar(c,sizeof(c),0);

    c[0]:=b[0]+dl;

    for i:=1 to b[0] do c:=b[i];

    larger:=bigger(a,c);

    end;

    procedure divi(var a,b,c:arr);

    begin

    fillchar(c,sizeof(c),0);

    while a[0]>0 do

    if a[0]>b[0] then

    if larger(a,b,a[0]-b[0]) then

    begin

    plus(c,a[0]-b[0]);

    minus(a,b,a[0]-b[0]);

    end

    else begin

    plus(c,a[0]-b[0]-1);

    minus(a,b,a[0]-b[0]-1);

    end

    else begin

    plus(c,a[0]-b[0]);

    minus(a,b,a[0]-b[0]);

    end;

    end;

    procedure out(a:arr);

    var i:longint;

    begin

    for i:=a[0] downto 1 do write(a[i]); writeln;

    end;

    begin

    getin;

    gcd(a,b);

    mul(a,b,w);

    if (g[0]=1) and (g[1]=1) then out(w)

    else begin

    divi(w,g,d);

    out(d);

    end;

    end.

    没有做高除 用的是在末尾添零的方法

    • @ 2013-02-20 22:00:54

      高精度压位

  • 0
    @ 2009-11-08 10:46:22

    巨恶心...各种高精度

    又不想写辗转相除,只好更相减损

    还好乘法不要四位一存否则...

    Flag   Accepted

    题号   P1047

    类型(?)   数论 / 数值

    通过   415人

    提交   5162次

    通过率   8%

    难度   2

    带文件的程序(除去起装饰用的空行250行+):

    #include

    #include

    #include

    FILE *in,*out;

    char a[330]={'\0'},b[330]={'\0'},zdgys[330]={'\0'},zxgbs[330]={'\0'},g1[330]={'\0'},g2[330]={'\0'},g3[330]={'\0'};

    long lona,lonb;

    short Max(char s1[],char s2[])

    {

    if (strlen(s1)strlen(s2)) return 1;

    if (strcmp(s1,s2)=0;j--)

    {

    l1=(short)(s1[lon1])-48-jw;

    l2=(short)(s2[lon2])-48;

    if (l1>=l2) jw=0;

    else

    {

    l1+=10;

    jw=1;

    }

    l1-=l2;

    jg[lon1]=(char)(l1+48);

    lon1--;

    lon2--;

    }

    while (jw!=0)

    {

    if (s1[lon1]=='0')

    {

    jg[lon1]=(char)(9+48);

    lon1--;

    }

    else

    {

    jg[lon1]=(char)((int)s1[lon1]-jw);

    jw=0;

    lon1--;

    }

    }

    if (lon1>=0)

    {

    for (j=lon1;j>=0;j--)

    jg[j]=s1[j];

    }

    k=0;lon3=strlen(jg);

    for (j=0;j

  • 0
    @ 2009-11-02 13:58:18

    高精大结合!!!!!!!!!!!!!!!!!!!!!!!!1

    program aa;

    var

    s,a,b,t,ccc,bbb:ansistring;

    function dayu(a,b:ansistring):boolean;

    begin

    if (length(a)>length(b)) or (length(a)=length(b)) and (a>b) then dayu:=true

    else dayu:=false;

    end;

    function max(a,b:ansistring):integer;

    begin

    if length(a)>length(b) then max:=length(a)

    else max:=length(b);

    end;

    function gjj(a,b:ansistring):ansistring;

    var

    s:ansistring;

    arr,brr,crr:array[0..10000] of integer;

    i,sum:integer;

    begin

    if a=b then gjj:='0'

    else

    begin

    gjj:='';

    fillchar(arr,sizeof(arr),0);

    fillchar(brr,sizeof(brr),0);

    fillchar(crr,sizeof(crr),0);

    for i:=1 to length(a) do

    arr[length(a)-i+1]:=ord(a[i])-ord('0');

    for i:=1 to length(b) do

    brr[length(b)-i+1]:=ord(b[i])-ord('0');

    sum:=1;

    crr[1]:=arr[1]-brr[1];

    while sum

  • 0
    @ 2009-10-23 20:22:42

    终于ac了.......

  • 0
    @ 2009-10-23 12:12:02

    没有写除法额。一次ac好激动啊。这题目真提神。。

    program vijos1047;

    type stack = array[0..10500] of longint;

    var a,b,ans,stan : stack;

    procedure chu(var a : stack);

    var t,i : longint;

    begin

    t := 0;

    for i := a[0] downto 1 do

    begin

    t := t*10+a[i];

    a[i] := t div 2;

    t := t mod 2;

    end;

    while a[a[0]] = 0 do dec(a[0]);

    end;

    function check(a,b:stack):boolean;

    var i : longint;

    begin

    if a[0] b[0] then exit(false);

    for i := 1 to a[0] do

    if a[i] b[i] then exit(false);

    exit(true);

    end;

    function compare(a,b:stack):boolean;

    var i : longint;

    begin

    if a[0] > b[0] then exit(true)

    else if a[0] < b[0] then exit(false);

    for i := a[0] downto 1 do

    if a[i] > b[i] then exit(true)

    else if a[i] < b[i] then exit(false);

    exit(false);

    end;

    procedure jian(var a,b:stack);

    var i : longint;

    begin

    for i := 1 to a[0] do

    begin

    if a[i] < b[i] then

    begin

    inc(a[i],10);

    dec(a);

    end;

    a[i] := a[i]-b[i];

    end;

    while a[a[0]] = 0 do dec(a[0]);

    end;

    function jia(a,b:stack):stack;

    var i,l : longint;

    c : stack;

    begin

    fillchar(c,sizeof(c),0);

    if a[0] > b[0] then l := a[0]

    else l := b[0];

    for i := 1 to l do

    begin

    c[i] := c[i] + a[i] + b[i];

    c := c + c[i] div 10;

    c[i] := c[i] mod 10;

    end;

    if c[l+1] 0 then c[0] := l+1

    else c[0] := l;

    jia := c;

    end;

    function cheng(a,b:stack):stack;

    var i,j : longint;

    c : stack;

    begin

    fillchar(c,sizeof(c),0);

    for i := 1 to a[0] do

    for j := 1 to b[0] do

    c := c + a[i] * b[j];

    i := 1;

    while (i= 10) do

    begin

    inc(c,c[i] div 10);

    c[i] := c[i] mod 10;

    inc(i);

    end;

    c[0] := i;

    cheng := c;

    end;

    procedure print;

    var i : longint;

    begin

    for i := ans[0] downto 1 do

    write(ans[i]);

    writeln;

    end;

    procedure work;

    var i,tot,p : longint;

    st : array[1..10000] of integer;

    begin

    fillchar(st,sizeof(st),0);

    tot := 0;

    while not check(a,b) do

    begin

    if (a[1] mod 2=0) and (b[1] mod 2 = 0) then

    begin

    chu(a);

    chu(b);

    inc(tot);

    st[tot] := 3;

    end else

    if a[1] mod 2 = 0 then

    begin

    chu(a);

    inc(tot);

    st[tot] := 4;

    end else

    if b[1] mod 2 = 0 then

    begin

    chu(b);

    inc(tot);

    st[tot] := 5;

    end else

    if compare(a,b) then

    begin

    inc(tot);

    st[tot] := 1;

    jian(a,b);

    end else

    begin

    inc(tot);

    st[tot] := 2;

    jian(b,a);

    end;

    end;

    ans := a;

    fillchar(a,sizeof(a),0);

    fillchar(b,sizeof(b),0);

    a[0] := 1; a[1] := 1;

    b[0] := 1; b[1] := 1;

    p := 0;

    for i := tot downto 1 do

    if st[i] = 1 then a := jia(a,b) else

    if st[i] = 2 then b := jia(a,b) else

    if st[i] = 3 then inc(p) else

    if st[i] = 4 then a := cheng(a,stan) else

    b := cheng(b,stan);

    ans := cheng(ans,a);

    ans := cheng(ans,b);

    for i := 1 to p do

    ans := cheng(ans,stan);

    print;

    end;

    procedure did;

    var i,t : longint;

    s,ss : string;

    begin

    fillchar(a,sizeof(a),0);

    fillchar(b,sizeof(b),0);

    fillchar(stan,sizeof(stan),0);

    stan[1] := 2;

    stan[0] := 1;

    readln(ss);

    t := pos(' ',ss);

    s := copy(ss,1,t-1);

    for i := 1 to length(s) do

    a[i] := ord(s[length(s)-i+1]) - 48;

    a[0] := length(s);

    delete(ss,1,t);

    for i := 1 to length(ss) do

    b[i] := ord(ss[length(ss)-i+1]) - 48;

    b[0] := length(ss);

    end;

    begin

    did;

    work;

    end.

  • 0
    @ 2009-10-21 21:34:22

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    const filename='p1047';

    type numtype=array[0..220]of longint;

    var

    s1,s2:string;

    a,b,c,d,e,h,m,t:numtype;

    i,j,k,last,i1,j1:longint;

    x,y,z,xx,yy:int64;

    function pan(c,d:numtype):boolean; //判断c和d的大小。c>d返回false 相等也是FALSE

    var i:longint; //c0)do dec(i);

    if i0 then

    begin

    if c[i]>d[i]then exit(false);

    if c[i]0)do //if e0) do dec(c[0]);

    if (c[0]=0)and(c[1]=0)then begin h:=d;exit;end;

    /// begin for i:=d[0]downto 1 do writeln(d[i]); close(input);close(output);halt end;

    if pan(c,d) then begin t:=c;c:=d;d:=t;{gcd(d,c);}break; end; ////如果c0)do //if e

  • 0
    @ 2009-10-26 18:12:39

    哎。。。。。。。。。

    我除法用二分答案。。。

    sunny交了7次。。。。。。

    然后 6K AC

  • 0
    @ 2009-10-18 17:37:18

    高精度减法 = BT;

    高精度减法 + 乘法 = Very BT;

    高精度减法 + 乘法 + 除法 = Very Very BT;

    高精度减法 + 乘法 + 除法(高精度除以高精度) = the most BT in the world

  • 0
    @ 2009-10-18 13:46:59

    小心,题目数据不厚道,测试数据9的两个数大于10^100。

    本题只要高精度除法写顺当了就没啥问题。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    #include

    using namespace std;

    typedef int array[301];

    array A,B;

    void cheng(array a,array b,array &c)

    {

    int i,j;

    memset(c,0,sizeof(c));

    for (i=1;i

  • 0
    @ 2009-10-10 15:38:45

    var

       a,b,r,m,n,min,t:integer;

    begin

    readln(a,b);

    if a

信息

ID
1047
难度
8
分类
高精度 点击显示
标签
(无)
递交数
7369
已通过
774
通过率
11%
被复制
24
上传者