D. Count GCD
题意
给定一个长度为 n n n 的正整数数组 a a a, ∀ 1 ≤ i ≤ n , a i ≤ m \forall 1 \leq i \leq n,a_i \leq m ∀1≤i≤n,ai≤m
先要要统计满足以下条件的数组 b b b 的数量:
- ∀ 1 ≤ i ≤ n , b i ≤ m \forall 1 \leq i \leq n,b_i \leq m ∀1≤i≤n,bi≤m
- g c d ( b 1 , b 2 , b 3 , . . . b i ) = a i gcd(b_1,b_2,b_3,...b_i) = a_i gcd(b1,b2,b3,...bi)=ai
思路
可以发现在当前的 i i i, g c d ( a 1 , a 2 , . . . a i − 1 ) = a i − 1 gcd(a_1,a_2,...a_{i -1}) = a_{i -1} gcd(a1,a2,...ai−1)=ai−1,那么只要 g c d ( a i − 1 , b i ) = a i gcd(a_{i - 1},b_i) = a_i gcd(ai−1,bi)=ai 就可以了,那么我们可以得出结论: a i ∣ a i − 1 a_i \mid a_{i - 1} ai∣ai−1,也即是 a i − 1 a_{i - 1} ai−1 是 a i a_i ai 的因子,同时 a i ∣ b i a_i \mid b_i ai∣bi
这样子答案就是每个位置可选的数量累乘,问题是如何快速求出位置 i i i 可行的 b i b_i bi 数量
b i b_i bi 一定得是 a i a_i ai 的倍数,我们可以假设 k ⋅ a i = b i k \cdot a_i = b_i k⋅ai=bi,那么不同的 k k k 的数量就是 b i b_i bi 的数量
那么 g c d ( a i − 1 , b i ) = a i ⇒ g c d ( a i − 1 a i , k ) = 1 gcd(a_{i - 1}, b_i) = a_i \Rarr gcd(\dfrac{a_{i - 1}}{a_i}, k) = 1 gcd(ai−1,bi)=ai⇒gcd(aiai−1,k)=1,也就是 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai−1 中出现的质因子不能在 k k k 中出现
为了快速得到 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai−1 的所有质因子,我们发现 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai−1 的质因子一定是 a 1 a_1 a1 的质因子。这是因为 a i ∣ a i − 1 ∣ . . . . ∣ a 2 ∣ a 1 a_i \mid a_{i - 1} \mid .... \mid a_2 \mid a_1 ai∣ai−1∣....∣a2∣a1;并且最小的 10 10 10 个质数相乘就已经大于 1 0 9 10^9 109 了!所以我们只需要最多 9 9 9 个不同的质数(不一定是最小的 9 9 9 个)就可以表示小于等于 1 0 9 10^9 109 的数了
我们只需要在 O ( m ) O(m) O(m) 下预处理 得出 a 1 a_1 a1 的质因子,然后对于每个 i > 2 i > 2 i>2,枚举 a 1 a_1 a1 的质因子,看看 a i a_i ai 是否被其整除,即可快速得出 a i a_i ai 的所有质因子,质因子数量都不超过 9 9 9 个!我们这里就可以考虑状压 + 容斥原理来计数了
容斥原理:
集合 S S S 的子集 A 1 A_1 A1 具有性质 P 1 P_1 P1,子集 A 2 A_2 A2 具有性质 P 2 P_2 P2,… A n A_n An 具有性质 P n P_n Pn
(1)集合 S S S 中不具有性质 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1,P2,...,Pn 的对象个数为:
∣ A 1 ‾ ∩ A 2 ‾ , . . . , ∩ A n ‾ ∣ = ∣ S ∣ − ∑ ∣ A i ∣ + ∑ ∣ A i ∩ A j ∣ − ∑ ∣ A i ∩ A j ∩ A k ∣ + . . . + ( − 1 ) n ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ | \overline{A_1} \cap \overline{A_2}, ..., \cap \overline{A_n}| = |S| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + ... + (-1)^{n} |A_1 \cap A_2 \cap ... \cap A_n| ∣A1∩A2,...,∩An∣=∣S∣−∑∣Ai∣+∑∣Ai∩Aj∣−∑∣Ai∩Aj∩Ak∣+...+(−1)n∣A1∩A2∩...∩An∣
(2)集合 S S S 中至少具有性质 P 1 , P 2 , . . . P n P_1,P_2,...P_n P1,P2,...Pn 之一的对象个数为:
∣ A 1 ∪ A 2 , . . . , ∪ A n ∣ = ∑ ∣ A i ∣ − ∑ ∣ A i ∩ A j ∣ + ∑ ∣ A i ∩ A j ∩ A k ∣ + . . . + ( − 1 ) n + 1 ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ | A_1 \cup A_2, ..., \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| + ... + (-1)^{n + 1} |A_1 \cap A_2 \cap ... \cap A_n| ∣A1∪A2,...,∪An∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣+...+(−1)n+1∣A1∩A2∩...∩An∣
因为性质很少,最多只有 9 9 9 个(分别被不同的 9 9 9 个质数整除),我们要求出与 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai−1 互质的 k k k 的数量,也就是 k k k 不能拥有 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai−1 的质因子,也就是 k k k 不具有性质 P 1 , P 2 , . . . P k P_1,P_2,...P_k P1,P2,...Pk( k k k 为 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai−1 质因子数),只需要用容斥原理简单地通过整除得到即可,注意 k ≤ m a i k \leq \dfrac{m}{a_i} k≤aim
时间复杂度: O ( m + 9 ⋅ 2 9 ⋅ log m ) O(\sqrt m + 9 \cdot 2^9 \cdot \log m) O(m+9⋅29⋅logm)
最后那个 log m \log m logm 是因为: a 1 a_1 a1 的每个质因子数量一定非递减,如果某个质因子在 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai−1 中出现,说明这个质因子数量在这里至少 − 1 -1 −1 了,那么从 a 1 a_1 a1 减少到 a n a_n an,质因子最多就 log m \log m logm 个,很快就没了
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;template<class T>
constexpr T power(T a, ll b){T res = 1;while(b){if(b&1) res = res * a;a = a * a;b >>= 1;}return res;
}constexpr ll mul(ll a,ll b,ll mod){ //快速乘,避免两个long long相乘取模溢出ll res = a * b - ll(1.L * a * b / mod) * mod;res %= mod;if(res < 0) res += mod; //误差return res;
}template<ll P>
struct MLL{ll x;constexpr MLL() = default;constexpr MLL(ll x) : x(norm(x % getMod())) {}static ll Mod;constexpr static ll getMod(){if(P > 0) return P;return Mod;}constexpr static void setMod(int _Mod){Mod = _Mod;}constexpr ll norm(ll x) const{if(x < 0){x += getMod();}if(x >= getMod()){x -= getMod();}return x;}constexpr ll val() const{return x;}explicit constexpr operator ll() const{ return x; //将结构体显示转换为ll类型: ll res = static_cast<ll>(OBJ)}constexpr MLL operator -() const{ //负号,等价于加上ModMLL res;res.x = norm(getMod() - x);return res;}constexpr MLL inv() const{assert(x != 0);return power(*this, getMod() - 2); //用费马小定理求逆}constexpr MLL& operator *= (MLL rhs) & { //& 表示“this”指针不能指向一个临时对象或const对象x = mul(x, rhs.x, getMod()); //该函数只能被一个左值调用return *this;}constexpr MLL& operator += (MLL rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLL& operator -= (MLL rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLL& operator /= (MLL rhs) & {return *this *= rhs.inv();}friend constexpr MLL operator * (MLL lhs, MLL rhs){MLL res = lhs;res *= rhs;return res;}friend constexpr MLL operator + (MLL lhs, MLL rhs){MLL res = lhs;res += rhs;return res;}friend constexpr MLL operator - (MLL lhs, MLL rhs){MLL res = lhs;res -= rhs;return res;}friend constexpr MLL operator / (MLL lhs, MLL rhs){MLL res = lhs;res /= rhs;return res;}friend constexpr std::istream& operator >> (std::istream& is, MLL& a){ll v;is >> v;a = MLL(v);return is;}friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){return os << a.val();}friend constexpr bool operator == (MLL lhs, MLL rhs){return lhs.val() == rhs.val();}friend constexpr bool operator != (MLL lhs, MLL rhs){return lhs.val() != rhs.val();}
};const ll mod = 998244353;
using Z = MLL<mod>;std::vector<int> get_d(int x){std::vector<int> d;for(int i = 2; i * i <= x; ++i){if(x % i ) continue;d.push_back(i);while(x % i == 0) x /= i;}if(x > 1) d.push_back(x);return d;
}void solve(){int n, m;std::cin >> n >> m;std::vector<int> a(n + 1);fore(i, 1, n + 1) std::cin >> a[i];fore(i, 2, n + 1)if(a[i - 1] % a[i]){std::cout << "0\n";return;}auto div = get_d(a[1]);Z ans = 1;fore(i, 2, n + 1){int val = a[i - 1] / a[i];std::vector<int> left;for(auto d : div)if(val % d == 0)left.push_back(d);int sz = left.size();ll K = m / a[i]; //k的上界ll tot = K;fore(mask, 1, 1 << sz){int cnt = __builtin_popcount(mask); //容斥原理系数int now = 1;fore(j, 0, sz)if(mask >> j & 1)now *= left[j];if(cnt & 1) tot -= K / now;else tot += K / now;}ans *= tot;}std::cout << ans << endl;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){solve();}return 0;
}