P10415（洛谷题面）

题目

题目描述：

给定一个 $W\times H$ 的长方形，两边长度均为整数。小蓝想把它切割为很多个边长为整数的小正方形。假设切割没有任何损耗，正方形的边长至少为 $2$ ，不允许出现余料，要求所有正方形的大小相等，请问最多能切割出多少个?

输入格式：

输入一行，包含两个整数 $W, H$ ，用一个空格分隔。

输出格式：

输出一行包含一个整数表示答案。如果不存在满足要求的方案，输出 $0$ 。

数据范围与说明：

【样例解释 1】

切割成 $5\times 10=50$ 个边长为 $2$ 的正方形。

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $1\le W,H\le 1000$ ；
对于 $60\%$ 的评测用例， $1\le W,H\le 10^6$ ；
对于所有评测用例， $1\le W,H\le 10^9$ 。

输入输出样例 #1

输入：

10 20

输出：

输入输出样例 #2

输入：

6 9

输出：

输入输出样例 #3

输入：

8 13

输出：

题意

简述：

代码

C++

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<int, int> PLL;
int gcd(int a,int b){
    return b? gcd(b,a%b):a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    ll n,m;
   cin>>n>>m;
    int w=gcd(n,m);//最大正方形的边长
    if(w==1){//如果两个都是质数那么不能完全分解
        cout<<0;
        return 0;
    }
    for(int i=2;i*i<=w;i++){//最大公约数便是最大正方形的面积，因此用i*i来比较 
        if(n%i==0&&m%i==0){
            cout<<n/i*m/i;
            return 0;
        }
    }
    cout<<n/w*m/w;//特判w是质数的情况
    return 0;
}

【题解】P10415

P10415（洛谷题面）

题目

题意

代码

C++