Codeforces Round #720 (Div. 2)
A. Nastia and Nearly Good Numbers
题意
能被 整除的数叫 good，能被 整除但不能被 整除的数叫 nearly good。找三个不同的正整数 ，满足 ，且恰好一个 good、两个 nearly good。
思路
时， 的倍数全是 good，凑不出 nearly good，直接无解。否则取 。
前两个加起来正好是第三个，除以 后分别是 ，所以前两个不能被 整除，第三个可以； 时三个数也都不一样。代码里先约了一下公因子，乘回去还是这三个数。
代码
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int T;
cin >> T;
while(T--) {
int A, B;
cin >> A >> B;
int g = gcd(A, B);
int a = A / g, b = B / g;
if(B != 1) cout << "YES" << endl << 1ll * (B - 1) * a * g << " " << 1ll * (B + 1) * a * g<< " " << 1ll * 2 * b * a * g * g << endl;
else cout << "NO" << endl;
}
return 0;
}B. Nastia and a Good Array
题意
要把数组改成相邻两个数都互质。每次可以选两个位置换成两个正整数，只要这两个数的最小值保持不变，操作次数不能超过 。
思路
找一个最小值 的位置 ，一直保留它。和 同奇偶的位置设成 ，另一种奇偶的位置设成 。相邻两个数连续，最大公约数就是 1。
每次都选当前的位置和 ，两数最小值仍然是 ，所以操作合法。除了 以外各改一次，一共 次。
代码
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 17;
int n, a[maxn], mn, p;
int main() {
int t; scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
mn = 0x3f3f3f3f;
for(int i = 1; i <= n; i++) mn = min(mn, a[i]);
for(int i = 1; i <= n; i++) if(a[i] == mn) p = i;
printf("%d\n", n - 1);
for(int i = 1; i <= n; i++) {
if(i == p) continue;
if((i & 1) == (p & 1)) printf("%d %d %d %d\n", i, p, mn, mn);
else printf("%d %d %d %d\n", i, p, mn + 1, mn);
}
}
return 0;
}