cf Problem - D - Codeforces
tag:容斥,分解质因子
题意： 题意：给定两个正整数$n,m(n <= 2e5)$，以及一个长度为n的数组 $a (1≤a_i≤m)$。计算满足以下条件且长度为$n$的数组 $b$。
- $1≤b_i≤m,∀i=1,⋯,n$
- $gcd(b_1,⋯,b_i)=a_i,∀i=1,⋯,n$
idea:
对$i>=2$，需要满足$a_i | a_{i-1}$，否则答案为0，同时每个$b_i$互相独立（不影响序列个数),乘起来即可
设$a_{i-1} = t a_i$ $b_i = ka_i$
要使$gcd(a_{i-1},b_i) = a_i$
则 $gcd(t,k) = 1$
求满足$gcd(t,k)=1 且 ka_i <= m$的数量
则$k <= \lfloor \frac{m}{a_i}\rfloor$
对$t$分解质因子，后暴力容斥即可
容斥思路：
因$m <= 1e9$ ,所以 $2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 > 6e9$，即最多取9个数容斥即可得到上界$m$
...接下来就是最讨厌的数数环节，设$\frac{a_{i-1}}{a_i}$ = $b$，首先对于其分解质因子（去重后），二进制枚举是否选，然后取其子集个数以及子集个数奇偶性取正负存起来即可
vector<array<ll,2>>divv(ll n)
{vector<ll>p;for(int i = 2;i * i <= n;i++){if(n % i == 0){p.push_back(i);while(n%i==0) n/=i;}}if(n > 1) p.push_back(n);n = p.size();vector<array<ll,2>>a(1<<n);a[0] = {1,1};for(int i = 1;i < (1ll<<n);i++){int j = __builtin_ctz(i);auto [x,y] = a[i ^ (1ll<<j)];a[i] = {x*p[j],-y};}return a;
}
然后注意一下a[i] == a[i-1]的特殊情况,即取a[i]的所有<=m的倍数即可
完整代码如下:
/*
首先暑假好热
其次暑假好热
最后暑假好热
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 200005;
const int inf = 0x3f3f3f;
typedef long long ll;
using pii = pair<int, int>;auto vec(int D) { return std::vector<int>(D); }
template<typename...R>
auto vec(int D, R...r) { return std::vector(D, vec(r...)); }//auto dp =vec(a,b,c);vector<array<ll,2>>divv(ll n)
{vector<ll>p;for(int i = 2;i * i <= n;i++){if(n % i == 0){p.push_back(i);while(n%i==0) n/=i;}}if(n > 1) p.push_back(n);n = p.size();vector<array<ll,2>>a(1<<n);a[0] = {1,1};for(int i = 1;i < (1ll<<n);i++){int j = __builtin_ctz(i);auto [x,y] = a[i ^ (1ll<<j)];a[i] = {x*p[j],-y};}return a;
}void graspppp()
{ll n,m;cin>>n>>m;vector<ll>a(n+1);ll ans = 1;for(int i = 1;i <= n;i++){cin>>a[i];if(i >= 2 && a[i-1] % a[i] != 0) ans = 0;}if(ans == 0) {cout<<"0\n";return ;}for(int i = 2;i <= n;i++){if(a[i] == a[i-1]){ans = (ans * (m /a[i])) % mod;}else{ll res = 0;auto g = divv(a[i-1]/a[i]);for(auto [x,u] : g){ res = (res + (u * (m/a[i]/x)+mod)%mod)%mod;// res %= mod;}ans *= res;ans %= mod;}}cout<<ans<<"\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T = 1;cin>>T;while (T--)graspppp();//cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n";return 0;
}