CF1665A题解

此文首发于洛谷

同步发于博客园

题目大意

有 t t t 组数据，每组数据给你一个正整数 n n n ，让你输出任意一组正整数 a a a ， b b b ， c c c ， d d d ，使得满足 gcd ⁡ ( a , b ) = lcm ⁡ ( c , d ) \gcd(a,b) = \operatorname{lcm}(c,d) gcd(a,b)=lcm(c,d) 并且 a + b + c + d = n a + b + c + d = n a+b+c+d=n

解法

首先特判 n n n 是否为 4 4 4 的倍数，若成立则令 a a a ， b b b ， c c c ， d d d 均为 n 4 \frac{n}{4} 4n​ 。

证明：

根据最大公约数和最小公倍数的性质： 若 a = b a = b a=b ， 则 gcd ⁡ ( a , b ) = a \gcd(a,b) = a gcd(a,b)=a ， lcm ⁡ ( a , b ) = a \operatorname{lcm}(a,b) = a lcm(a,b)=a 。

∴ \therefore ∴ gcd ⁡ ( a , b ) = lcm ⁡ ( c , d ) = n 4 \gcd(a,b) = \operatorname{lcm}(c,d) = \frac{n}{4} gcd(a,b)=lcm(c,d)=4n​ 并且 a + b + c + d = n a + b + c + d = n a+b+c+d=n 。

不成立则开始枚举 a a a ， b b b ， c c c 。

d d d 可以通过 n − a − b − c n - a - b - c n−a−b−c 得到，不用进行 4 4 4 重循环。

a a a 从 n 2 \frac{n}{2} 2n​ 开始枚举到 1 1 1 ， b b b 从 n − a n - a n−a 开始枚举到 1 1 1 ， c c c 从 n − a − b n - a - b n−a−b 开始枚举到 1 1 1 。

并且枚举 b b b 时若 n − a − b < 2 n - a - b < 2 n−a−b<2 进入下一个循环，枚举 c c c 时若 n − a − b − c < 1 n - a - b - c < 1 n−a−b−c<1 进入下一个循环。

对于上述 *** 作的解释： 因为这道题目的要求是存在解即可输出。

所以 a a a 从 n 2 \frac{n}{2} 2n​ 开始枚举可以保证 b + c + d b + c + d b+c+d 一定大于等于 n 2 \frac{n}{2} 2n​ ，同时减少了时间复杂度。

b b b 与 c c c 的枚举方式同样减少了时间复杂度。

对于 枚举 b b b 时的特判是因为若 n − a − b < 2 n - a - b < 2 n−a−b<2 则 d d d 不成立，枚举 c c c 时的特判是因为若 n − a − b − c < 1 n - a - b - c < 1 n−a−b−c<1 则 d d d 不成立。

在枚举出 a a a ， b b b ， c c c ， d d d 后若满足 gcd ⁡ ( a , b ) = lcm ⁡ ( c , d ) \gcd(a,b) = \operatorname{lcm}(c,d) gcd(a,b)=lcm(c,d) 则输出答案并进入下一组数据。

代码

#include
using namespace std;

int n,a,b,c,d,t;
bool flag = false;

int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}

int lcm(int x,int y){
    return x * y / gcd(x,y);
}

int main()
{
    cin >> t;
    while(t--){
        cin >> n;
        if(n%4==0){
            a = n/4;
            b = a;
            c = b;
            d = c;
            cout << a << " " << b << " " << c << " " << d << endl;
            continue;
        }
        flag = false;
        for(a = n/2;a>=1;a--){
            for(b = n - a;b>=1;b--){
                if(a+b>n-2){
                    continue;
                }
                for(c = n - a - b;c>=1;c--){
                    if(n-a-b-c<1){
                        continue;
                    }
                    d = n - a - b - c;
                    if(gcd(a,b)==lcm(c,d)){
                        cout << a << " " << b << " " << c << " " << d << endl;
                        flag = true;
                        break;
                    }
                }
                if(flag){
                    break;
                }
            }
            if(flag){
                break;
            }
        }
    }
    return 0;
}