#include<bits/stdc++.h>
using namespace std;
unsigned long long gcd(unsigned long long a,unsigned long long b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int main(){
    for(int i=1;i<=10;i++){
        unsigned long long A,B;
        cin>>A>>B;
        cout<<A+B-gcd(A,B)<<"\n";
    }
    return 0;
}

正文前提示

由于输入范围在 $-\textbf{2}^{\textbf{63}}\sim\textbf{2}^{\textbf{63}}-\textbf1$，所以一定要开开 unsigned long long！不然会 $\textbf{30}$ 分！！！

题目传送门

主要思路

这是一道带有贪心思想的题。分析后，我们发现目标是让我们尽可能少地划分出正方形。也就是说，划分出的正方形的边长要尽可能的大。那么划分出的正方形的边长就为 $\min\left(a,b\right)$。

那么一个长方形内有多少边长为 $\min\left(a,b\right)$ 的正方形呢？我们可以把长方形分割成 $k$ 个边长为 $\min\left(a,b\right)$ 的正方形，把这 $k$ 个正方形边长累加到答案里去，然后让长方形的长（也就是 $\max\left(a,b\right)$）减去 $k\times\min\left(a,b\right)$，直到长方形的任意一边被减到 $0$，输出答案即可。

那么这个 $k$ 怎么求呢？其实很简单，根据下面这幅图，就可以推断出是 $\left\lfloor\dfrac{\max\left(a,b\right)}{\min\left(a,b\right)}\right\rfloor$。

接下来就是代码实现了。

AC code

#include<iostream>
#define ull unsigned long long
using namespace std;
int main(){
    for(int i=1;i<=10;i++){
        ull a,b,ans=0;
        cin>>a>>b;
        while(a!=0&&b!=0){//两条边没有到 0 的时候不要停。
            ull k=max(a,b)/min(a,b);//依思路
            ans+=(k*min(a,b));
            if(a==max(a,b))a-=(k*min(a,b));
            else b-=(k*min(a,b));
        }
        cout<<ans<<'\n';
    }
    return 0;
}