为什么只能过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;
}

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

水到不行的题，呵呵
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));
}
}
```

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