14062: 【原4062】日天圈地

题目描述

author: AimAlex 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4062

Description

日天学长由于在各方面方面表现出色，中央决定奖励他一块矩形的耕地。

日天学长得到这块耕地之后，不幸染上了强迫症。他要把这个耕地分为若干个正方形，并且要把这些正方形用篱笆围起来，围出每一个正方形所消耗篱笆的长度即为这个正方形的周长。（注意：对于两个小正方形的公共边，按两层篱笆计算。因此篱笆的总长度即为分成的所有小正方形的周长之和）

日天学长为了省下一些钱去约会，希望能够尽可能减少篱笆的长度。请你帮他设计一个方案。

Input Format

两个正整数x,y，表示矩形耕地的两边长。

对于50%的数据，x,y < 10^4；对于100%的数据，x,y < 10^16；

Output Format

一个正整数z，表示所需要篱笆的最小长度（即为所分成的所有小正方形的周长之和）

Sample Input

1 2

Sample Output

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/17.
//
// 辗转相除

#include <iostream>
#include <algorithm>

using namespace std;

static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

using ll=long long;

ll get(ll a, ll b) {
    if (b == 0)
        return 0;
    ll adb = a / b;
    ll adbmb = adb * b;
    return 4 * adb * b + get(b, a - adbmb);
}

int main() {
    ll a, b;
    cin >> a >> b;
    if (a < b) swap(a, b);
    cout << get(a, b);
    return 0;
}

FineArtz's solution

/* 日天圈地 */
#include <iostream>
using namespace std;

long long f(long long x, long long y){
    long long t, ret;
    if (x > y){
        t = x;
        x = y;
        y = t;
    }
    ret = 4 * x * (y / x);
    y = y % x;
    if (y == 0) return ret;
    else return ret + f(y, x);
}

int main(){
    long long x, y, ans;
    cin >> x >> y;
    ans = f(x, y);
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

long long cal(long long x, long long y) {
    if (y == 0 || x == 0)
        return 0;
    if (y >= x) {
        return cal(x, y % x) + y / x * x * 4;
    }
    else {
        return cal(x % y, y) + x / y * y * 4;
    }
}

int main() {
    long long x, y;
    cin >> x >> y;

    cout << cal(x, y);

    return 0;
}

q4x3's solution

/**
 * 模拟
 * 将矩形较短的边作为正方形边长
 * 注意long long
 **/
#include <iostream>

using namespace std;

long long m, n, ans;
int main() {
    cin >> m >> n;
    while(m != 0 || n != 0) {
        if(m == n) {
            ans += 4 * m;
            break;
        }
        if(m > n) {
            ans += 4 * n;
            m = m - n;
        }
        if(m < n) {
            ans += 4 * m;
            n = n - m;
        }
    }
    cout << ans << endl;
}

skyzh's solution

#include <iostream>
using namespace std;

int main() {
    long long x, y, res = 0;
    cin >> x >> y;
    while (x > 0) {
        if (x < y) swap(x, y);
        res += y * 4;
        long long c = x - y;
        x = y; y = c;
    }
    cout << res << endl;
    return 0;
}

victrid's solution

#include <iostream>
using namespace std;
long long seq(long long x, long long y) {
    if (x < y)
        return seq(y, x);
    if (y == 0)
        return 0;
    return x / y * 4 * y + seq(y, x % y);
}
int main() {
    long long x, y;
    cin >> x >> y;
    cout << seq(x, y);
    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
long long a,b;
long long x(long long a,long long b)
{
    if (b!=0)
        return a/b*4*b+x(b,a%b);
    else return 0;
}
int main() {
    cin>>a>>b;
    cout<<x(a,b);
    return 0;
}