这是我有时以来编的最长的程序,92行,激励自己

为什么只能过5 组?

递归的时候栈竟然爆了？-.=

.

重庆NOI2005选拔第一题.

欧几里德算法。

恶心人的高精度除法

稍微一不注意就会出错

开始有两个点TLE，还以为需要优化

结果一看，交换时的位数变量没交换

因为这个提交了n多次~~~~:(

典型的传统gcd欧几里德算法求出最大公约数。

然后很容易得出最小公倍数。

需要注意的是应采用高精度乘除法，这就要靠自己细心了。

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    for(int i=max(a,b);i<=a*b;i++)
    {
        if(i%a==0&&i%b==0) return i;
    }
}
int main()
{
    int x,y;
    cin>>x>>y;
    cout<<gcd(x,y);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    for(int i=max(a,b);i<=a*b;i++)
    {
        if(i%a==0&&i%b==0) return i;
    }
}
int main()
{
    int x,y;
    cin>>x>>y;
    cout<<gcd(x,y);
    return 0;
}

水到不行的题，呵呵
python随便写秒过。
高精度是什么？？

def gcd(a,b):
    if a < b:
        temp = b
        b = a 
        a = temp
    remainder = a % b
    if remainder == 0:
        return b
    else:
        return gcd(remainder,b)

def gys(a,b):
    remainder = gcd(a,b)
    print(a*b//remainder)

a,b=map(int,input().split())
gys(a,b)

个人思路是找大值然后更迭为最大值的倍数，直到更迭到某一次正好能被小值整除就是解集。WA的原因我觉得应该是longlong型不够大。

前四个都是对的，后面就都WA了，求solution

#include <iostream>

using namespace std;

int main(){
    long long int  m,n;
    while(cin>>m>>n){
        int ans=max(m,n);
        int tmp=min(m,n);
        long long int sum=ans;
        while(1){
            if(sum%tmp==0){
                cout<<sum<<endl;
                break;
            }
            sum+=ans;
        }
    }
    return 0;
}

这个测试有bug 手动测试没有问题

这边给一下思路，首先我们通过计算得出

最小公倍数 = （最大公因数）*（a/最大公因数）*（b/最大公因数）

20 12 = 4* (20/4) * (12/4)=60

这个时候我们把最小公倍数问题转换成了最大公因数问题
关于最大公因数我们可以通过亚里士多德算法（大概是这个名字）
即
while (lsb!=0) {
ys = lsb;
lsb = a % lsb;
}

得出公约数代入公式返回公倍数

//laotan 原创 转载请注明出处
#include <iostream>
using namespace std;

int bs(int a, int b) {
    int n = 0, ys, ls = 0 , lsb = b;

    if (a<b) {
        ls = b;
        b = a;
        a = ls;
    }

    if (a%b == 0) return a;
        
    while (lsb!=0) {
        ys = lsb;
        lsb = a % lsb;
    }

    return (ys*(a/ys)*(b/ys));
}

int main()
{
    int a, b;
    cin >> a >> b;

if (a<b) {
    int ls;
    ls = b;
    b = a;
    a = ls;
}
cout << bs(a, b) << endl;

 }

from math import *
a,b = map(int,input().split())
print(a * b // gcd( a , b))

python 无敌

高精度gcd,mod,div
求lcm通过求gcd实现
```cpp
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
const double eps=1e-8;

struct bignum {
int len;
int a[350];
bignum() {
len=0;
memset(a,0,sizeof a);
}
void operator=(bignum x) {
len=x.len;
memset(a,0,sizeof a);
FOR(i,len) a[i]=x.a[i];
}
bool operator==(bignum x) {
if (len!=x.len) return 0;
FOR(i,len) if (a[i]!=x.a[i]) return 0;
return 1;
}
bignum operator-(bignum x) {
// 要先确保被减数大于等于减数
bignum res;
res.len=len;
FOR(i,299) res.a[i]=a[i];
FOR(i,res.len) {
res.a[i]-=x.a[i];
if (res.a[i]<0) {
res.a[i+1]--,res.a[i]+=10;
}
}
while (res.a[res.len]==0&&res.len) res.len--;
if (res.len==0) res.len=1;
return res;
}
bignum operator*(bignum x) {
bignum res;
FOR(i,len) FOR(j,x.len) {
res.a[i+j-1]+=a[i]*x.a[j];
}
res.len=len+x.len-1;
FOR(i,res.len) {
if (res.a[i]>9) {
res.a[i+1]+=res.a[i]/10;
res.a[i]%=10;
}
}
if (res.a[res.len+1]) res.len++;
return res;
}
bool operator<(bignum x) {
if (len<x.len) return 1;
else if (len>x.len) return 0;
for (int i=len;i>=1;i--) {
if (a[i]<x.a[i]) return 1;
else if (a[i]>x.a[i]) return 0;
}
return 0;
}
bignum operator+(bignum x) {
bignum res;
res.len=max(len,x.len);
FOR(i,res.len) {
res.a[i]=a[i]+x.a[i];
if (res.a[i]>9) {
res.a[i+1]++;
res.a[i]-=10;
}

}
if (res.a[res.len+1]) res.len++;
return res;
}
};
void print(bignum x) {
for (int i=x.len;i>=1;i--) cout<<x.a[i];
cout<<endl;
}
bignum zero;
bignum ten[201];
bignum mo(bignum x,bignum y) {
for (int i=100;i>=0;i--) {
for (int j=9;j>=1;j--) {
bignum t;
t.len=1,t.a[1]=j;

if (!(x<ten[i]*y*t)) {
x=x-ten[i]*y*t;
break;
}
}
}
return x;
}
bignum div(bignum x,bignum y) {
// 确保能整除
bignum res;
for (int i=200;i>=0;i--) {
for (int j=9;j>=1;j--) {
bignum t;
t.len=1,t.a[1]=j;

if (!(x<ten[i]*y*t)) {
//print(x);
x=x-ten[i]*y*t;
res=res+ten[i]*t;
//print(ten[i]*t);
break;
}
}
}
return res;
}
bignum bgcd(bignum x,bignum y) {
if (x<y) {
bignum t=y;
y=x;
x=t;
}
if (y==zero) return x;
else return bgcd(y,mo(x,y));
}
bignum turn(string s) {
bignum res;
for (int i=s.size()-1;i>=0;i--) {
res.a[++res.len]=s[i]-'0';
}
return res;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
zero.len=1;
REP(i,0,200) {
ten[i].len=i+1;
ten[i].a[i+1]=1;
}
string s1,s2;
cin>>s1>>s2;
bignum x=turn(s1),y=turn(s2);
//print(x*y);
//print(bgcd(x,y));
print(div(x*y,bgcd(x,y)));
return 0;
}
```

Java大法好*2

import java.math.BigInteger;
import java.util.Scanner;

public class Main 
{
    private static BigInteger gcd(BigInteger A, BigInteger B) 
    {
        if (B.equals(BigInteger.ZERO))
            return A;
        
        return gcd(B, A.mod(B));
    }
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        
        BigInteger A = in.nextBigInteger(), B = in.nextBigInteger();
        System.out.println(A.multiply(B).divide(gcd(A, B)));
        
        in.close();
    }
}

#pragma GCC optimize("inline",3)
#include<bits/stdc++.h> Fuko Ibuki
namespace chtholly{//fast input and output
#define ll long long
#define p32 putchar(' ')
#define pl puts("")
const double ten[]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15,1e16,1e17,1e18,1e19};
int read(){int x=0;char c=getchar();for (;!isdigit(c);c=getchar());for (;isdigit(c);c=getchar()) x=x*10+c-'0';return x;}
int write(int x){if (!x) return putchar('0');int bit[20],i,p=0;for (;x;x/=10) bit[++p]=x%10;for (i=p;i;--i) putchar(bit[i]+48);}
int read(double &r){double x=0,t=0;int s=0,f=1;char c=getchar();for (;!isdigit(c);c=getchar()){if (c=='-') f=-1;if (c=='.') goto readt;}for (;isdigit(c)&&c!='.';c=getchar()) x=x*10+c-'0';readt:for (;c=='.';c=getchar());for (;isdigit(c);c=getchar()) t=t*10+c-'0',++s;r=(x+t/ten[s])*f;}
int read(ll &x){x=0;char c=getchar();for (;!isdigit(c);c=getchar());for (;isdigit(c);c=getchar()) x=x*10+c-'0';}
int dwrite(ll x){if (x==0) return putchar(48);int bit[20],p=0,i;for (;x;x/=10) bit[++p]=x%10;for (i=p;i>0;--i) putchar(bit[i]+48);}
int write(double x,int k=6){static int n=ten[k];if (x==0) {putchar('0'),putchar('.');for (int i=1;i<=k;++i) putchar('0');return 0;}if (x<0) putchar('-'),x=-x;ll y=(ll)(x*n)%n;x=(ll)x;dwrite(x),putchar('.');int bit[20],p=0,i;for (;p<k;y/=10) bit[++p]=y%10;for (i=p;i>0;--i) putchar(bit[i]+48);}
#undef ll
};
using namespace chtholly;
using namespace std;
#define kasumi 1000
typedef long long ll;
int n;

struct boss{
int len,num[500],nev;
boss(){len=1,memset(num,0,sizeof num);nev=0;}
void print()
  {
  if (nev==1) putchar('-');
  for (int i=len;i>=1;i--) putchar(num[i]+48);
  }
};

boss operator *(boss a,boss b)
{
boss c;int i;
for (i=1;i<=a.len;i++) for (int j=1;j<=b.len;j++) c.num[i+j-1]+=a.num[i]*b.num[j]; 
for (i=1;i<=a.len+b.len-1;i++) 
  {
  c.num[i+1]+=c.num[i]/10;
  c.num[i]%=10;
  }
for (;c.num[i]==0;i--);
c.len=i;
return c;
}

int operator <(boss a,boss b)
{
if (a.len<b.len) return 1;
else if (a.len>b.len) return 0; 
for (int i=a.len;i>0;i--) 
  if (a.num[i]<b.num[i]) return 1;
  else if (a.num[i]>b.num[i]) return 0;
return 0;
}

boss operator +(boss a,boss b)
{
boss c;int len=max(a.len,b.len);
for (int i=1;i<=len;++i) c.num[i]=a.num[i]+b.num[i];
for (int i=1;i<=len;++i) 
  {
  c.num[i+1]+=c.num[i]/10,c.num[i]%=10;
  if (i==len&&c.num[i+1]>0) len++;
  }
c.len=len;
return c;
}

boss operator *(boss a,int b)
{
boss c;int len=a.len,i;
for (i=1;i<=len;++i) c.num[i]=a.num[i]*b;
for (i=1;i<=len;i++)
  {
  c.num[i+1]+=c.num[i]/10;
  c.num[i]%=10;
  if (i==len&&c.num[i+1]>0) len++;
  }
c.len=len;
return c;
}

boss operator -(boss a,boss b)
{
boss c;c.len=max(a.len,b.len);int i;
for (i=1;i<=c.len;i++) c.num[i]=a.num[i]-b.num[i];
for (i=c.len;i>=1;i--) if (c.num[i]<0)
  {
  int j=i;
  c.num[i]+=10,c.num[i+1]--;
  while (c.num[j+1]<0) c.num[j+1]+=10,c.num[j+2]--,j++;
  }
while (c.num[c.len]==0&&c.len>1) c.len--;
return c;
}

boss operator /(boss a,int b)
{
boss c;int cmp=0,nico=0,i;
for (i=a.len;i>0;--i) 
  {
  cmp=cmp*10+a.num[i];
  cmp>=b?(nico=1,c.num[++c.len]=cmp/b,cmp%=b):nico==1?c.num[++c.len]=0:0;
  }
for (;c.num[c.len]==0;c.len--);
reverse(c.num+1,c.num+c.len+1);
return c;
}

boss operator /(boss a,boss b)
{
boss c,d;d.len=1;
for (int i=a.len;i>0;--i)
  {
  d=d*10;d.num[1]=a.num[i];
  for (;!(d<b);) c.num[i]++,d=d-b;
  }
for (c.len=a.len-b.len+1;c.len<4000&&c.num[c.len]!=0;++c.len);c.len--;
return c;
}

void read(boss &a)
{
int t=0;char c=getchar();
for (;!isdigit(c);c=getchar());
for (;isdigit(c);c=getchar()) a.num[++t]=c-'0';
a.len=t;reverse(a.num+1,a.num+t+1);
}

boss gcd(boss a,boss b)
{
boss c;c.len=1,c.num[1]=1;
if (a<b) swap(a,b);
for (;b.len!=1||b.num[1]!=0;)
  {
  if (!(a.num[1]&1))
    {
    if (!(b.num[1]&1)) c=c*2,a=a/2,b=b/2;
    else a=a/2;
    } 
  else 
    {
    if (!(b.num[1]&1)) b=b/2;
    else a=a-b;
    }
  if (a<b) swap(a,b);
  }
return c*a;
}

void yuefen(boss &a,boss &b)
{
boss c=gcd(a,b);
a=a/c,b=b/c;
}

boss lcm(boss a,boss b){return a*b/gcd(a,b);}

int main()
{
boss a,b;
read(a),read(b);
lcm(a,b).print();
}

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

py dafahao
```python
import sys
def gcd(a,b):
if b == 0:
return a
else:
return gcd(b,a%b)

a,b = map(int, input().split())
print(a*b//gcd(max(a,b),min(a,b)))
```

Haskell大法好（自带高精）

gbs [] = 1
gbs (x:xs) = lcm x $ gbs xs
main = print . gbs . map read . words =<< getLine

java大法好
```java
import java.util.*;
import java.math.*;

public class Main {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);

String s1=sc.next();
String s2=sc.next();
BigInteger a=new BigInteger(s1);
BigInteger b=new BigInteger(s2);
BigInteger c=new BigInteger(a.gcd(b).toString());

System.out.println(a.multiply(b).divide(c));
}
}
```

马志！！！！！！！！马志！！！！！！！！！！！！！！！！！！！！！！