1226题解——贪心

解题思路:
分奇偶两种情况考虑。

注意事项:

参考代码:

#include <stdio.h>
#include <iostream>
 
using namespace std;
 
int gcd(int a, int b){
    int t;
    for(int i = 1; i <= a && i <= b; i++){
        if(a%i == 0 && b % i == 0){
            t = i;
        }
    }
    return t;
}
 
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int l;
        scanf("%d", &l);
        if(l % 2 == 0){
            printf("4\n");
        }else{
            int max = 1;
            int s1;
            for(int j = 1; j <= l/2; j++){
                if(max <= gcd(j, l-j)){
                    s1 = j;
                    max = gcd(j, l-j);
                }
            }
            int res = 2;
            int x = l-s1, y = s1;
            while(x > 0 && y > 0){
                if(x > y){
                    res += 2 * (x/y);
                    x %= y;
                }else{
                    res += 2 * (y/x);
                    y %= x;
                }
            }
            printf("%d\n", res);
            return 0;
        }
    }
}