自动搬运

查看原文

来自洛谷，原作者为

	huangyuze114514 deep♂dark♂fantasy♂

搬运于2025-08-24 22:57:45，当前版本为作者最后更新于2024-06-14 18:46:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

求出 $W,N$ 的大于等于 $2$ 的最小公因数，把大于等于 $2$ 的最小公因数分别除 $W,N$，得出的两个数相乘即为所求。

所以我们按照思路写一篇代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	long long n,m;
	cin>>n>>m;
	for(long long i=2;;i++){
		if(n%i==0&&m%i==0){
			cout<<n/i*m/i;
			return 0;
		}
	}
	return 0;
}

发现超时了，因为本题数据较大，暴力显然不能过，所以要有一点优化。

代码如下

#include <bits/stdc++.h>
using namespace std;
int main(){
	long long n,m;
	cin>>n>>m;
	int a=__gcd(n,m);//求最大公约数 
	if(a==1){//互质不符合题目条件 
		cout<<0;
		return 0;
	}
	for(int i=2;i*i<=a;i++){//最大公约数便是最大正方形的边长，因此用i*i来比较 
		if(n%i==0&&m%i==0){
			cout<<n/i*m/i;
			return 0;
		}
	}
	cout<<n/a*m/a;//没有符合条件便输出最大正方形的解 
	return 0;
}