/ Vijos / 题库 / 最小公倍数 /

题解

167 条题解

  • 0
    @ 2009-09-01 16:14:14

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var a,b,c,i:int64;

    begin

    　　readln(a,b);

    　　if a

  • 0
    @ 2009-08-18 16:05:41

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    高精大团圆，耐心+细心=秒杀

    先求高精gcd

    再求lcm:=a/gcd(a,b)*b

  • 0
    @ 2009-08-11 09:52:34

    type

    　　arr=array[-1..400]of integer;

    var

    　　ans,a,b:arr;

    procedure init;

    　　var

    　　 i:integer;

    　　 s1,s2:string;

    　　begin

    　　 readln(s2);

    　　 s1:=copy(s2,1,pos(' ',s2)-1);

    　　 a[0]:=length(s1);

    　　 for i:=1 to a[0] do a[a[0]+1-i]:=ord(s1[i])-48;

    　　 delete(s2,1,pos(' ',s2));

    　　 b[0]:=length(s2);

    　　 for i:=1 to b[0] do b[b[0]+1-i]:=ord(s2[i])-48;

    　　end;

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

    　　var

    　　 i:integer;

    　　 c:arr;

    　　begin

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

    　　 if a[0]0 then inc(c[0]);

    　　 jia:=c;

    　　end;

    function jian(a,b:arr):arr;

    　　var

    　　 i:integer;

    　　 c:arr;

    　　begin

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

    　　 for i:=1 to a[0] do

    　　　　begin

    　　　　 if a[i]1) do dec(c[0]);

    　　 jian:=c;

    　　end;

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

    　　 var

    　　 i,j:integer;

    　　 c:arr;

    　　 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];

    　　 c[0]:=a[0]+b[0]-1;

    　　 for i:=1 to c[0] do

    　　　　 begin

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

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

    　　　　 end;

    　　 while c[c[0]+1]0 do

    　　　　 begin

    　　　　 inc(c[0]);

    　　　　 c[c[0]+1]:=c[c[0]] div 10;

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

    　　　　 end;

    　　 cheng:=c;

    　　 end;

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

    　　 var i:integer;

    　　 begin

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

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

    　　 for i:=a[0] downto 1 do

    　　　　 if a[i]b[i] then

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

    　　　　　　　　　　　　 else exit(false);

    　　 exit(false);

    　　 end;

    procedure move1(var a,b:arr);

    　　 var i:integer;

    　　 begin

    　　 while compare(a,b) do

    　　　　 begin

    　　　　 inc(b[0]);

    　　　　 for i:=b[0] downto 2 do

    　　　　　　 b[i]:=b;

    　　　　 inc(b[-1]);

    　　　　 b[1]:=0;

    　　　　 end;

    　　 if compare(b,a) then

    　　　　 begin

    　　　　 for i:=1 to b[0]-1 do

    　　　　　　 b[i]:=b;

    　　　　 b[b[0]]:=0;

    　　　　 dec(b[0]);

    　　　　 dec(b[-1]);

    　　　　 end;

    　　 end;

    procedure move2(var a,b:arr);

    　　 var i:integer;

    　　 begin

    　　 while (compare(b,a)) and (b[-1]>0) do

    　　　　 begin

    　　　　 for i:=1 to b[0]-1 do

    　　　　　　 b[i]:=b;

    　　　　 b[b[0]]:=0;

    　　　　 dec(b[-1]);

    　　　　 dec(b[0]);

    　　　　 end;

    　　 end;

    function chu(a,b:arr):arr;

    　　 var

    　　 c:arr;

    　　 begin

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

    　　 move1(a,b);

    　　 while not compare(b,a) do

    　　　　 begin

    　　　　 a:=jian(a,b);

    　　　　 inc(c[b[-1]+1]);

    　　　　 if b[-1]+1>c[0] then c[0]:=b[-1]+1;

    　　　　 if b[-1]>0 then move2(a,b);

    　　　　 end;

    　　 chu:=c;

    　　 end;

    function yu(a,b:arr):arr;

    　　 begin

    　　 move1(a,b);

    　　 while not compare(b,a) do

    　　　　 begin

    　　　　 a:=jian(a,b);

    　　　　 move2(a,b);

    　　　　 end;

    　　 yu:=a;

    　　 end;

    function gcd(a,b:arr):arr;

    　　 var t:arr;

    　　 begin

    　　 while compare(a,b) or compare(b,a) do

    　　　　 begin

    　　　　 if compare(b,a) then

    　　　　　　 begin

    　　　　　　 t:=a;

    　　　　　　 a:=b;

    　　　　　　 b:=t;

    　　　　　　 end;

    　　　　 if (b[0]=1) and (b[1]=0) then exit(a);

    　　　　 if (b[0]=1) and (b[1]=1) then exit(b);

    　　　　 a:=yu(a,b);

    　　　　 end;

    　　 gcd:=a;

    　　 end;

    function lcm(a,b:arr):arr;

    　　 var

    　　 ji,g:arr;

    　　 begin

    　　 ji:=cheng(a,b);

    　　 g:=gcd(a,b);

    　　 lcm:=chu(ji,g);

    　　 end;

    procedure outit;

    　　 var i:integer;

    　　 begin

    　　 for i:=ans[0] downto 1do

    　　　　 write(ans[i]);

    　　 end;

    begin

    　　init;

    　　ans:=lcm(a,b);

    　　outit;

    end.

  • 0
    @ 2009-08-03 14:47:20

    type

    　　arr=array[-1..400]of integer;

    var

    　　ans,a,b:arr;

    procedure init;

    　　var

    　　 i:integer;

    　　 s1,s2:string;

    　　begin

    　　 readln(s2);

    　　 s1:=copy(s2,1,pos(' ',s2)-1);

    　　 a[0]:=length(s1);

    　　 for i:=1 to a[0] do a[a[0]+1-i]:=ord(s1[i])-48;

    　　 delete(s2,1,pos(' ',s2));

    　　 b[0]:=length(s2);

    　　 for i:=1 to b[0] do b[b[0]+1-i]:=ord(s2[i])-48;

    　　end;

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

    　　var

    　　 i:integer;

    　　 c:arr;

    　　begin

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

    　　 if a[0]0 then inc(c[0]);

    　　 jia:=c;

    　　end;

    function jian(a,b:arr):arr;

    　　var

    　　 i:integer;

    　　 c:arr;

    　　begin

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

    　　 for i:=1 to a[0] do

    　　　　begin

    　　　　 if a[i]1) do dec(c[0]);

    　　 jian:=c;

    　　end;

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

    　　 var

    　　 i,j:integer;

    　　 c:arr;

    　　 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];

    　　 c[0]:=a[0]+b[0]-1;

    　　 for i:=1 to c[0] do

    　　　　 begin

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

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

    　　　　 end;

    　　 while c[c[0]+1]0 do

    　　　　 begin

    　　　　 inc(c[0]);

    　　　　 c[c[0]+1]:=c[c[0]] div 10;

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

    　　　　 end;

    　　 cheng:=c;

    　　 end;

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

    　　 var i:integer;

    　　 begin

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

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

    　　 for i:=a[0] downto 1 do

    　　　　 if a[i]b[i] then

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

    　　　　　　　　　　　　 else exit(false);

    　　 exit(false);

    　　 end;

    procedure move1(var a,b:arr);

    　　 var i:integer;

    　　 begin

    　　 while compare(a,b) do

    　　　　 begin

    　　　　 inc(b[0]);

    　　　　 for i:=b[0] downto 2 do

    　　　　　　 b[i]:=b;

    　　　　 inc(b[-1]);

    　　　　 b[1]:=0;

    　　　　 end;

    　　 if compare(b,a) then

    　　　　 begin

    　　　　 for i:=1 to b[0]-1 do

    　　　　　　 b[i]:=b;

    　　　　 b[b[0]]:=0;

    　　　　 dec(b[0]);

    　　　　 dec(b[-1]);

    　　　　 end;

    　　 end;

    procedure move2(var a,b:arr);

    　　 var i:integer;

    　　 begin

    　　 while (compare(b,a)) and (b[-1]>0) do

    　　　　 begin

    　　　　 for i:=1 to b[0]-1 do

    　　　　　　 b[i]:=b;

    　　　　 b[b[0]]:=0;

    　　　　 dec(b[-1]);

    　　　　 dec(b[0]);

    　　　　 end;

    　　 end;

    function chu(a,b:arr):arr;

    　　 var

    　　 c:arr;

    　　 begin

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

    　　 move1(a,b);

    　　 while not compare(b,a) do

    　　　　 begin

    　　　　 a:=jian(a,b);

    　　　　 inc(c[b[-1]+1]);

    　　　　 if b[-1]+1>c[0] then c[0]:=b[-1]+1;

    　　　　 if b[-1]>0 then move2(a,b);

    　　　　 end;

    　　 chu:=c;

    　　 end;

    function yu(a,b:arr):arr;

    　　 begin

    　　 move1(a,b);

    　　 while not compare(b,a) do

    　　　　 begin

    　　　　 a:=jian(a,b);

    　　　　 move2(a,b);

    　　　　 end;

    　　 yu:=a;

    　　 end;

    function gcd(a,b:arr):arr;

    　　 var t:arr;

    　　 begin

    　　 while compare(a,b) or compare(b,a) do

    　　　　 begin

    　　　　 if compare(b,a) then

    　　　　　　 begin

    　　　　　　 t:=a;

    　　　　　　 a:=b;

    　　　　　　 b:=t;

    　　　　　　 end;

    　　　　 if (b[0]=1) and (b[1]=0) then exit(a);

    　　　　 if (b[0]=1) and (b[1]=1) then exit(b);

    　　　　 a:=yu(a,b);

    　　　　 end;

    　　 gcd:=a;

    　　 end;

    function lcm(a,b:arr):arr;

    　　 var

    　　 ji,g:arr;

    　　 begin

    　　 ji:=cheng(a,b);

    　　 g:=gcd(a,b);

    　　 lcm:=chu(ji,g);

    　　 end;

    procedure outit;

    　　 var i:integer;

    　　 begin

    　　 for i:=ans[0] downto 1do

    　　　　 write(ans[i]);

    　　 end;

    begin

    　　init;

    　　ans:=lcm(a,b);

    　　outit;

    end.

  • 0
    @ 2009-07-26 10:15:42

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    type

    arr=array[-1..400]of integer;

    var

    ans,a,b:arr;

    procedure init;

    var

    i:integer;

    s1,s2:string;

    begin

    readln(s2);

    s1:=copy(s2,1,pos(' ',s2)-1);

    a[0]:=length(s1);

    for i:=1 to a[0] do a[a[0]+1-i]:=ord(s1[i])-48;

    delete(s2,1,pos(' ',s2));

    b[0]:=length(s2);

    for i:=1 to b[0] do b[b[0]+1-i]:=ord(s2[i])-48;

    end;

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

    var

    i:integer;

    c:arr;

    begin

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

    if a[0]0 then inc(c[0]);

    jia:=c;

    end;

    function jian(a,b:arr):arr;

    var

    i:integer;

    c:arr;

    begin

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

    for i:=1 to a[0] do

    begin

    if a[i]1) do dec(c[0]);

    jian:=c;

    end;

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

    var

    i,j:integer;

    c:arr;

    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];

    c[0]:=a[0]+b[0]-1;

    for i:=1 to c[0] do

    begin

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

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

    end;

    while c[c[0]+1]0 do

    begin

    inc(c[0]);

    c[c[0]+1]:=c[c[0]] div 10;

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

    end;

    cheng:=c;

    end;

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

    var i:integer;

    begin

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

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

    for i:=a[0] downto 1 do

    if a[i]b[i] then

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

    else exit(false);

    exit(false);

    end;

    procedure move1(var a,b:arr);

    var i:integer;

    begin

    while compare(a,b) do

    begin

    inc(b[0]);

    for i:=b[0] downto 2 do

    b[i]:=b;

    inc(b[-1]);

    b[1]:=0;

    end;

    if compare(b,a) then

    begin

    for i:=1 to b[0]-1 do

    b[i]:=b;

    b[b[0]]:=0;

    dec(b[0]);

    dec(b[-1]);

    end;

    end;

    procedure move2(var a,b:arr);

    var i:integer;

    begin

    while (compare(b,a)) and (b[-1]>0) do

    begin

    for i:=1 to b[0]-1 do

    b[i]:=b;

    b[b[0]]:=0;

    dec(b[-1]);

    dec(b[0]);

    end;

    end;

    function chu(a,b:arr):arr;

    var

    c:arr;

    begin

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

    move1(a,b);

    while not compare(b,a) do

    begin

    a:=jian(a,b);

    inc(c[b[-1]+1]);

    if b[-1]+1>c[0] then c[0]:=b[-1]+1;

    if b[-1]>0 then move2(a,b);

    end;

    chu:=c;

    end;

    function yu(a,b:arr):arr;

    begin

    move1(a,b);

    while not compare(b,a) do

    begin

    a:=jian(a,b);

    move2(a,b);

    end;

    yu:=a;

    end;

    function gcd(a,b:arr):arr;

    var t:arr;

    begin

    while compare(a,b) or compare(b,a) do

    begin

    if compare(b,a) then

    begin

    t:=a;

    a:=b;

    b:=t;

    end;

    if (b[0]=1) and (b[1]=0) then exit(a);

    if (b[0]=1) and (b[1]=1) then exit(b);

    a:=yu(a,b);

    end;

    gcd:=a;

    end;

    function lcm(a,b:arr):arr;

    var

    ji,g:arr;

    begin

    ji:=cheng(a,b);

    g:=gcd(a,b);

    lcm:=chu(ji,g);

    end;

    procedure outit;

    var i:integer;

    begin

    for i:=ans[0] downto 1do

    write(ans[i]);

    end;

    begin

    init;

    ans:=lcm(a,b);

    outit;

    end.

    //终于AC了……好高兴！

  • 0
    @ 2009-07-08 10:01:02

    program ex1;

    var

    a,b,c,d,e,f:longint;

    begin

    read(a,b);

    if a

  • 0
    @ 2009-07-02 14:03:11

    无聊的题目！！！

  • 0
    @ 2009-05-30 19:56:28

    高精度gcd,千万不能递归!!!

    编译通过...

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

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

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

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

    ├ 测试数据 05：运行时错误...| 错误号: 202 | 堆栈溢出错

    ├ 测试数据 06：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 07：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 08：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 09：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 10：运行时错误...| 错误号: 106 | 无效数字格式

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

    Unaccepted 有效得分：40 有效耗时：0ms

    用递归就这结果！！！！！！！！！！！！！！！！！！！！！！！！！！！！

  • 0
    @ 2009-05-29 08:29:25

    出现灵异事件了！

    第一次提交，首先显示为80分，打开结果后，发现2个点202一个点超时，分数变成了70！

    第二次用数组模拟栈，显示AC了。打开结果后，发现超时两个点，分数变为80！

    然而Flag显示为AC！好奇怪！

    这道题用到了高精度乘法、高精度除法、高精度模运算、高精度最大公约数、高精度数比较大小，可谓是高精度题的经典中的经典哦！

  • 0
    @ 2009-05-13 18:10:42

    试数据 02：答案正确... 0ms

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

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

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

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

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

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

  • 0
    @ 2009-05-02 15:15:07

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    本人第一次高精度除法,取模。都在这儿了。幸好一次AC。。。

  • 0
    @ 2009-04-30 13:54:39

    var a,b,c,i:int64;

    begin

    readln(a,b);

    if a

  • 0
    @ 2009-04-13 10:54:44

    第一次写运算符重载。。

    除法直接二分结果（我比较猥琐）

  • 0
    @ 2009-07-13 11:06:38

    数据太大了，肯定要高精度！！！！！！！！！！！！！！！！！

    即使用Qword直接gcd也只能得50分！！！！！！！！！！！！！

    题号 　　P1047

    类型(?) 　　数论 / 数值

    通过 　　313人

    提交 　　3956次

    通过率 　　8%

  • 0
    @ 2009-03-30 20:09:41

    变态题高精加、高精减、高精乘、高精MOD、高精DIV，怪不得froger大牛有393行，而且只有8%的通过率

    • @ 2017-02-08 17:04:17

      用python看起来也就那么几行呀？

  • 0
    @ 2009-05-30 20:34:34

    Var

    a,b,c,e,f,g:Int64;

    Begin

    Readln(a,b);

    e:=a;f:=b;g:=0;

    c:=0;c:=a Mod b;

    While c0 Do

    Begin

    a:=b;

    b:=c;

    c:=a Mod b;

    End;

    e:=e Div b;

    f:=f Div b;

    g:=e*f*b;

    Writeln(g);

    End.

    编译通过...

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

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

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

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

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

    ├ 测试数据 06：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 07：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 08：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 09：运行时错误...| 错误号: 106 | 无效数字格式

    ├ 测试数据 10：运行时错误...| 错误号: 106 | 无效数字格式

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

    Unaccepted 有效得分：50 有效耗时：0ms

    求高手帮忙看看哪儿错了,谢!

  • 0
    @ 2009-03-27 19:50:14

    直接高精度加GCD递归是不可以的，有3个数据说202错误………………

    郁闷了我5次才AC

  • 0
    @ 2009-03-21 11:39:23

    终于过了!!!!!

    我的高精度除法阿~~~

    把a*b/gcd(a,b)改成 a/gcd(a,b)*b 再优化了半天才过的..

  • 0
    @ 2009-03-02 16:54:24

    模板的力量！！

  • 0
    @ 2009-02-27 16:04:53

    var c,e,f,g:longint;

    　　a,b,d,h:qword;

    begin

    readln(e,f);

    a:=e;

    b:=f;

    d:=a-1;

    repeat

    　　d:=d+1;

    　　if (d mod a=0) and (d mod b =0) then begin

    　　 writeln(d);

    　　 break;

    　　end;

    until d=a*b;

    end.

最小公倍数

信息

ID
1047
难度
8
分类
高精度 点击显示
标签
(无)
递交数
7456
已通过
787
通过率
11%
被复制
29
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1