CF1665A题解
Crab_time
·
·
题解
题目大意
有 t 组数据，每组数据给你一个正整数 n ，让你输出任意一组正整数 a ， b ， c ， d ，使得满足 \gcd(a,b) = \operatorname{lcm}(c,d) 并且 a + b + c + d = n
解法
首先特判 n 是否为 4 的倍数，若成立则令 a ， b ， c ， d 均为 \frac{n}{4} 。
证明：
根据最大公约数和最小公倍数的性质： 若 a = b ， 则 \gcd(a,b) = a ， \operatorname{lcm}(a,b) = a 。
不成立则开始枚举 $a$ ， $b$ ， $c$ 。 $d$ 可以通过 $n - a - b - c$ 得到，不用进行 $4$ 重循环。 $a$ 从 $\frac{n}{2}$ 开始枚举到 $1$ ， $b$ 从 $n - a$ 开始枚举到 $1$ ， $c$ 从 $n - a - b$ 开始枚举到 $1$ 。并且枚举 $b$ 时若 $n - a - b < 2$ 进入下一个循环，枚举 $c$ 时若 $n - a - b - c < 1$ 进入下一个循环。
对于上述操作的解释： 因为这道题目的要求是存在解即可输出。所以 $a$ 从 $\frac{n}{2}$ 开始枚举可以保证 $b + c + d$ 一定大于等于 $\frac{n}{2}$ ，同时减少了时间复杂度。 $b$ 与 $c$ 的枚举方式同样减少了时间复杂度。对于 枚举 $b$ 时的特判是因为若 $n - a - b < 2$ 则 $d$ 不成立，枚举 $c$ 时的特判是因为若 $n - a - b - c < 1$ 则 $d$ 不成立。
在枚举出 $a$ ， $b$ ， $c$ ， $d$ 后若满足 $\gcd(a,b) = \operatorname{lcm}(c,d)$ 则输出答案并进入下一组数据。
# 代码
```cpp
#include<iostream>
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;
}
```