Codeforces Round 905 (Div. 2)

Codeforces Round 905 (Div. 2)"/>

Codeforces Round 905 (Div. 2)

B. Raspberries

注意到k只能是2，3，4，5

特判

如果存在一个数ai，满足ai % k ==0。那么操作数为0

（1） K=2,3,5时

因为2，3，5都是素数，所以要想使得a1~an的积能被k整除：a数组中一定有一个数ai，满足ai % k == 0。所以要想满足条件，最小值为 min( k - ai % k ）

（2）K=4时

注意到4 = 2 * 2；所以要想使得a1~an的积能被k整除：操作的数量最大只能是2。
在满足特判的情况下，我们统计a数组中偶数的个数cnt_even。
1、如果cnt_even>2，那么一定存在两个数ai和aj，他们的公因子中都含有2。那么乘积的因子中一定含有4。此时输出为0。
2、如果cnt_even == 1，那么此时a数组中只含有一个偶数。那么我们只需要随便把一个奇数加1，即可满足a数组中的两个数因子都含有2。此时输出为1。
3、如果cnt_even==0，那么此时a数组中全部是奇数。此时通过情况（1）中得到的ans结果要么是1，要么是3。输出min(ans , 2)即可。
因为ans如果是3的情况下，比如1 ， 1 ， 1
那么我们任选两个奇数加一，即可得到4。操作的次数是2。

#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
#define de(x) cout << x << " ";
#define sf(x) scanf("%d", &x);
#define Pu puts("");
#define ll long long
int n, m, ans;
int a[N];
int k;
int main() {int T;cin >> T;while (T--) {cin >> n >> k;int x;  // 输入ans = 1e9;int cnt_even = 0;  // 4对应的判断bool is_mod = false;for (int i = 1; i <= n; i++) {sf(x);if (x % k == 0)is_mod = true;ans = min(ans, k - x % k);  // 2，3，5对应的判断if (x % 2 == 0)cnt_even++;}if (is_mod == true) {printf("0\n");continue;}if (k == 4) {// 通过取模得到的ans要么是1，要么3，要么是2if (cnt_even > 1)  // 如果ans是2，说明全是偶数printf("0\n");else if (cnt_even == 1)  // 此时只有一个奇数printf("1\n");else  // 如果是1或者3，说明全是偶数，此时的ans最大是2cout << min(2, ans) << endl;} else {printf("%d\n", ans);}}return 0;
}