10.1题解

题解ZCC种田

题目描述：田地是一个巨大的矩形，然而zzc 每次只能种一个正方形,而每种一个正方形时zzc所花的体力值是正方形的周长，种过的田不可以再种，zzc很懒还要节约体力去泡妹子，想花最少的体力值去种完这块田地，问最小体力值。
例：输入：1 10
输出：40
数据范围：1<=x,y<=10^16
思路：
根据题目要求，首先种的区域是正方形，也就是规定好了边长是要相等的，也就是说我们需要找到在这个矩形里面最大的正方形，然后把它抠出来，接着重复这个操作，不断寻找着剩下矩形中最大的正方形。从而得到最终答案。
一开始得到这个思路，一个正方形一个正方形的切割，提交时发现有一个测试时间超出了，所以必须要优化这个规模。而通过分析发现，正方形的切割存在着重复操作，如果把这个重复给删除了，直接一步到位，那这个时间就大大缩短了。最终得到以下ac代码。

#include
using namespace std;
long long x,y;
long long ans;
int main(){cin>>x>>y;while(x!=0&&y!=0){if(x>y){ans+=((x/y)*4*y);x%=y;}else{ans+=((y/x)*4*x);y%=x;}} cout<<ans<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！