#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;
}

#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;
}

import math;print(math.gcd(int(input()),int(input())))

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));
        }
    }
}

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)

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.

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.

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个点。（我又说过了）。

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

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.

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

巨恶心...各种高精度

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

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

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

高精大结合!!!!!!!!!!!!!!!!!!!!!!!!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

终于ac了.......

没有写除法额。一次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.

编译通过...

├ 测试数据 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

哎。。。。。。。。。

我除法用二分答案。。。

sunny交了7次。。。。。。

然后 6K AC

高精度减法 = BT；

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

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

高精度减法 + 乘法 + 除法（高精度除以高精度） = the most BT in the world

小心，题目数据不厚道，测试数据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

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

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

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

var

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

begin

readln(a,b);

if a

高精度啊高精度啊高精度啊高精度啊高精度啊高精高精度啊度高精度啊高精度啊啊

太烦了太烦了太烦了太烦了太烦了太烦了太烦了太烦了太烦了太烦了太烦了太烦了太烦了