B. GCD Problem
题意
/(T (1 /le T /le 100000)/) 组数据，给定一个数字 /(n (10 /le n /le 10^9)/)，请你找出三个不同的正整数 /(a, b, c/) 满足 /(a + b + c = n/)，并且 /(gcd(a, b) = c/)。
SOLUTION
思路一：
首先想到对 /(n/) 分解质因数，然后枚举 /(c/)，但是这样复杂度是不太对的。 考虑固定 /(c = 1/)，然后题目转化为枚举 /(a, b/)，即将 /(n – 1/) 分成两个互质的数字的和/((a,b /ge 2)/)，由于 /(n-1/)不可能是很多质数的倍数，因此暴力枚举 /(a,b/) 即可。
代码一：
点击查看代码
inline void solve() {
int n; read(n);
for(int i = 2; ; i ++ ) if(gcd(i, n - i - 1) == 1) {
printf("%d %d %d/n", i, n - i - 1, 1);
break;
}
}
思路二
分析和思路一一样，但是我们可以随机化！
代码二
点击查看代码
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n; cin >> n;
while (true) {
// 生成 (2 - n - 2) 的随机数
int a = rnd() % (n - 3) + 2;
// int a = uniform_int_distribution<int>(2, n - 2)(rnd);
int b = n - a - 1;
if (a != 1 && b != 1 && __gcd(a, b) == 1) {
cout << a << " " << b << " " << 1 << "/n";
break;
}
}
}
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/289524.html