CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) D. Count GCD

题目链接：Problem - D - Codeforces

题目大意：

t (1≤t≤100)组测试，每组给定n 和 m (1≤n≤2⋅10^5, 1≤m≤10^9)，n表示数组的长度，下一行为a数组a1,a2,…,an (1≤ai≤m)。

要求构造长度为n的b数组，满足：

• 1≤bi≤m
• gcd(b1,b2,b3,...,bi)=ai

在给定a的情况下，每组输出满足条件b数组的个数，答案对998244353取模。

样例输入：

5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2

输出：

3
1
0
595458194
200000000

hint: 

测试1：

b数组为：[4,2,1];[4,2,3];[4,2,5].

思路：

首先，一定有b1=a1；对于i>1，有： 

 

 于是问题转化为对于每一个bi，在之间有多少个数与互素。

可以考虑计算不互素的个数，再用总数减去即可。

令s=，t= ，将s分解出的质数存入p数组中，根据容斥原理，总数为：

 可以用集合枚举的方式计算。

 时间复杂度：

最坏情况下，枚举每个bi，s分解出的素数个数最多为9个（前十个乘积已经超过1e9），集合枚举复杂度为9*2^9，所有测试组n的和最多为2e5，总复杂度为：

这样算会超时，但实际上分解出素数为9个的情况很少，而且算法瓶颈就是分解出素数的个数，枚举时也可以加一些判断优化，实测能AC。

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const LL MOD=998244353;
const int N=2e5+10;
int a[N],p[40],cnt;
void solve()
{
	int n,m;
	cin>>n>>m;
	rep(i,0,n) cin>>a[i];
	int ans=1;
	rep(i,1,n){
		int s=a[i-1]/a[i],t=m/a[i];
		if(s==0||a[i-1]%a[i]){
			cout<<0<
			return;
		}
		if(s==1){
			ans=1ll*ans*t%MOD;
			continue;
		}
		int cnt=0,res=0;
		rep(j,2,s/j+1){
			if(s%j==0) p[cnt++]=j;
			while(s%j==0) s/=j;
		}
		if(s>1) p[cnt++]=s;
		rep(i,1,1<
			int c=0;
			LL su=1;
			rep(j,0,cnt) if((i>>j)&1){
				++c,su*=p[j];
				if(su>t) break;
			}
			if(c&1) res+=t/su;
			else res-=t/su;
		}
		ans=1ll*ans*(t-res)%MOD;
	}
	cout<
}
int main()
{
//	#ifndef ONLINE_JUDGE
//    freopen("title.in","r",stdin);
//    freopen("title.out","w",stdout);
//    #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
//	rep(i,1,_+1){
//		cout<<"Case "<
//		solve();
//	}
	return 0;
}