代码实现：# include<iostream># include<bits/stdc++.h>using namespace std;# define int long long# define endl "\n"const int N = 2e5 + 10, mod = 998244353;int a[N];//在[1,top]范围内 ， 找和n互质的数的个数int cal(int n,int top){ vector<pair<int,int>> divisors;//质因子 for(int i = 2;i*i<=n;++i){if(n%i == 0){int s= 0;while(n%i == 0) n/=i,s++;divisors.push_back({i,s});//i的s次} } if(n>1) divisors.push_back({n,1}); int res = 0,m = divisors.size(); for(int i = 1;i< (1<<m);++i)//二进制模拟第j个元素选还是不选{int t = 1,s = 0;for(int j = 0;j < m;++j){if(i>>j&1){if(t*divisors[j].first>top){t = -1;break;}t *= divisors[j].first;s++;}}if(t != -1){if(s%2) res += top/t;//如果选了奇数个元素就是加else res -= top/t;//偶数个元素是减//从容斥原理可以得到} } return top-res;}void solve() { int n,m; cin>>n>>m; for(int i = 1;i <= n;++i) cin>>a[i]; for(int i = 2;i <= n;++i){if(a[i-1]%a[i]){cout<<0<<endl;return;} } int ans = 1; for(int i = 2;i <= n;++i){if(a[i] == a[i-1]){ans = ans*(m/a[i])%mod;}else{int t = cal(a[i-1]/a[i],m/a[i]);ans = ans*t%mod;} } cout<<ans<<endl;}int tt;signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); tt = 1; cin >> tt; while (tt--)solve(); return 0;}
推荐阅读
- 树上差分-边差分 P2680 [NOIP2015 提高组] 运输计划
- 电动牙刷的日常维护经验 科学延长电动牙刷的使用寿命
- 维护品牌形象的话 怎么维护品牌形象
- 中国叫一次消防车多少钱 叫一次消防车多少钱
- 您如何维护电动消防车 叫一次消防车多少钱
- 青少年维护国家安全的例子 青少年怎么样维护国家安全
- 长式周期表是什么意思 汽车维护周期表是什么意思
- 微信系统维护咋回事 微信系统维护怎么办
- 正确维护自动变速器 自动变速器的维护保养
- 长城精灵方向机的日常维护 长城精灵方向机总成多少钱