2021牛客暑期多校训练营2

J Product of GCDs

题目链接

题意

给定一个集合S，在S中找出元素个数为k的子集合T，计算T中所有元素的GCD（最大公约数），将所有的T得到的GCD乘在一起得到结果，结果对P取模。

思路

计算每一个可能的GCDg对最终答案的贡献。

考虑元素个数为k且GCD为g的子集合T，T里面的所有元素$T_i$一定都是g的倍数。

注意 如果$T_i$是$g\times x(x>1)$的倍数，那么GCD的值就是$g\times x$。

定义一个变量tmp = 0，tmp加上S中g的倍数的个数，然后tmp减去$g\times x$​的倍数的个数（容斥），则满足该条件的T的个数为$C_{tmp}^k$​。

那么g对结果的贡献就是$g^{C_{tmp}^k}$​，g的幂很大，要用到欧拉降幂。

这个时间卡的很紧

• 不用快读会炸。
• 取模时有可能也会炸，一些地方要换成while(x - mod >= mod) x -= mod。

AC的代码

#include<bits/stdc++.h>
using namespace std;
#define ll long longconst int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;inline ll read() {ll s = 0;char ch = getchar();while (ch < 48 || ch>57)ch = getchar();while (ch > 47 && ch < 58)s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();return s;
}ll n, k, p, phi_p, res;
ll factor[100], total = 0;// 计算p的约数
ll dp[N], cnt[N], c[N][32];
//===============================================================板子 
// 快速乘 
ll mul(ll a, ll b, ll mod) {return ((a * b - (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod;
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// 快速幂
ll power(ll a, ll b, ll c) {ll res = 1;while (b) {if (b & 1) {res = mul(res, a, c);}b >>= 1;a = mul(a, a, c);}return res % c;
}
int a[] = { 2, 3, 5, 7, 11 };
// 判断一个数是否为质数
bool miller_rabin(ll n) {if (n == 1) return 0;for (int i = 0; i < 5; ++i) {if (n == a[i]) return 1;if (!(n % a[i])) return 0;}ll d = n - 1;while (!(d & 1)) d >>= 1;for (int i = 1; i <= 5; ++i) {ll a = rand() % (n - 2) + 2;bool tmp_k = false;ll tmp_d = d;ll tmp = power(a, tmp_d, n);if (tmp == 1)	tmp_k = true;// 先把所有的2给提出来，然后在一个一个乘上去，这样比直接做快while (tmp != 1 && tmp != n - 1 && tmp_d != n - 1) {tmp = mul(tmp, tmp, n);tmp_d <<= 1;}// 二次探测if (tmp == n - 1)	tmp_k = true;if (!tmp_k)return 0;}return 1;
}
// 找出n的一个因数
const int M = (1 << 7) - 1;// 一个玄学值
ll pollard_rho(ll n) {for (int i = 0; i < 5; ++i) if (n % a[i] == 0) return a[i];ll x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;for (int k = 2; ; k <<= 1, y = x) {ll q = 1;// k用于倍增for (int i = 1; i <= k; ++i) {x = (mul(x, x, n) + a) % n;// f(x) = x^2+aq = mul(q, abs(x - y), n);// 每一次的|x-y|累加// 如果次数超过Mif (!(i & M)) {t = gcd(q, n);if (t > 1) break;}}if (t > 1 || (t = gcd(q, n)) > 1) break;}return t;
}
// 找出x的所有因数
void find(ll x) {if (x == 1 || x <= 0) return;if (miller_rabin(x)) {factor[++total] = x;return;}ll p = x;while (p == x) p = pollard_rho(x);while (x % p == 0) x /= p;find(p);// 递归遍历所有的因数find(x);
}
// 组合数
ll C(ll n, ll k) {if (n < k)return 0;return c[n][k];
}
//===============================================================int main() {int t = read();while (t--) {memset(cnt, 0, sizeof cnt);// ==============================================================输入n = read(); k = read(); p = read();ll maxn = -inf;// 数组中最大值for (int i = 1; i <= n; i++) {ll tmp = read();cnt[tmp]++;maxn = max(maxn, tmp);}// ==============================================================计算phires = 1;total = 0;find(p);// 寻找p的约数phi_p = p;// 计算phi(p)for (int i = 1; i <= total; i++) {phi_p = phi_p / factor[i] * (factor[i] - 1);}// ==============================================================组合数c[0][0] = 1;for (int i = 1; i <= n; i++) {c[i][0] = 1;if (i <= 31)	c[i][i] = 1;// k的值不会超过30，不需要计算更多位for (int j = 1; j < i && j <= 31; j++) {c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]);// 组合数的递推公式while (c[i][j] - phi_p >= phi_p) c[i][j] -= phi_p;}}// ==============================================================计算答案// 计算每个i对答案的贡献for (int i = maxn; i >= 1; i--) {int tmp = 0;// i的倍数for (int j = i; j <= maxn; j += i) {tmp += cnt[j];}dp[i] = C(tmp, k);for (int j = i + i; j <= maxn; j += i) {dp[i] -= dp[j];// 容斥}dp[i] = dp[i] % phi_p;if (dp[i] < 0)dp[i] = (dp[i] % phi_p + phi_p) % phi_p;res = mul(res, power(i, dp[i], p), p);}printf("%lld\n", res);}return 0;
}

一些要用到的板子

快速乘

ll mul(ll a, ll b, ll mod) {return ((a * b - (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod;
}

快速幂

ll power(ll a, ll b, ll c) {ll res = 1;while (b) {if (b & 1) {res = mul(res, a, c);}b >>= 1;a = mul(a, a, c);}return res % c;
}

miller_rabin-快速判断一个数是否为质数

int a[] = { 2, 3, 5, 7, 11 };
bool miller_rabin(ll n) {if (n == 1) return 0;for (int i = 0; i < 5; ++i) {if (n == a[i]) return 1;if (!(n % a[i])) return 0;}ll d = n - 1;while (!(d & 1)) d >>= 1;for (int i = 1; i <= 5; ++i) {ll a = rand() % (n - 2) + 2;bool tmp_k = false;ll tmp_d = d;ll tmp = power(a, tmp_d, n);if (tmp == 1)	tmp_k = true;// 先把所有的2给提出来，然后在一个一个乘上去，这样比直接做快while (tmp != 1 && tmp != n - 1 && tmp_d != n - 1) {tmp = mul(tmp, tmp, n);tmp_d <<= 1;}// 二次探测if (tmp == n - 1)	tmp_k = true;if (!tmp_k)return 0;}return 1;
}

pollard_rho-找出一个数的一个因数

// 找出n的一个因数
int a[] = { 2, 3, 5, 7, 11 };
const int M = (1 << 7) - 1;// 一个玄学值
ll pollard_rho(ll n) {for (int i = 0; i < 5; ++i) if (n % a[i] == 0) return a[i];ll x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;for (int k = 2; ; k <<= 1, y = x) {ll q = 1;// k用于倍增for (int i = 1; i <= k; ++i) {x = (mul(x, x, n) + a) % n;// f(x) = x^2+aq = mul(q, abs(x - y), n);// 每一次的|x-y|累加// 如果次数超过Mif (!(i & M)) {t = gcd(q, n);if (t > 1) break;}}if (t > 1 || (t = gcd(q, n)) > 1) break;}return t;
}
// 找出x的所有因数
void find(ll x) {if (x == 1 || x <= 0) return;if (miller_rabin(x)) {factor[++total] = x;return;}ll p = x;while (p == x) p = pollard_rho(x);while (x % p == 0) x /= p;find(p);// 递归遍历所有的因数find(x);
}