目前这题 C++ 题解全都可以被下面数据 hack：
1 100000000000000000
1 100000000000000000
1 100000000000000000
1 100000000000000000
1 100000000000000000
1 100000000000000000
1 100000000000000000
1 100000000000000000
1 100000000000000000
1 100000000000000000所以这里提供一份可以通过数据和 hack 的 C++ 题解。
考虑贪心。很显然把一个边长为 的正方形劈开一定不会更好，因此考虑贪心的在长方形中选取最大的正方形。发现这就是辗转相除法，因此直接按辗转相除法模拟即可。时间复杂度为 其中 为数据组数。
给个图方便理解：
笑点解析：不开 unsigned long long 拿 ，时间复杂度错了拿 。
// #pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
const int N=4010;
signed main(){
// freopen("1.out","w",stdout);
cin.tie(0)->sync_with_stdio(false);
for(int tc=0;tc<10;++tc){
int a,b;cin>>a>>b;
unsigned int sum=0;
while(a&&b){
if(a>b)swap(a,b);
sum+=1ull*(b/a)*a;b%=a;
}
cout<<sum<<'\n';
}
}
喜欢的话，留下你的评论吧～