P10415（洛谷题面）

题目

题目描述：

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

输入格式：

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

输出格式：

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

数据范围与说明：

【样例解释 1】

切割成 5×10=505\times 10=50 个边长为 22 的正方形。

【评测用例规模与约定】

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

输入输出样例 #1

输入：

1
10 20

输出：

1
50

输入输出样例 #2

输入：

1
6 9

输出：

1
6

输入输出样例 #3

输入：

1
8 13

输出：

1
0

题意

简述：

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

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}