1 条题解
-
0
正文前提示
由于输入范围在 $-\textbf{2}^{\textbf{63}}\sim\textbf{2}^{\textbf{63}}-\textbf1$,所以一定要开开
unsigned long long
!不然会 分!!!
主要思路
这是一道带有贪心思想的题。分析后,我们发现目标是让我们尽可能少地划分出正方形。也就是说,划分出的正方形的边长要尽可能的大。那么划分出的正方形的边长就为 。
那么一个长方形内有多少边长为 的正方形呢?我们可以把长方形分割成 个边长为 的正方形,把这 个正方形边长累加到答案里去,然后让长方形的长(也就是 )减去 ,直到长方形的任意一边被减到 ,输出答案即可。
那么这个 怎么求呢?其实很简单,根据下面这幅图,就可以推断出是 $\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
- 上传者