1 条题解

  • 0
    @ 2025-4-2 22:05:09

    正文前提示

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


    题目传送门

    主要思路

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

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

    那么这个 kk 怎么求呢?其实很简单,根据下面这幅图,就可以推断出是 $\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;
    }
    
    • 1

    信息

    ID
    36195
    时间
    1000ms
    内存
    512MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者