[容斥][数论]Count GCD Codeforces1750D

You are given two integers 𝑛n and 𝑚m and an array 𝑎a of 𝑛n integers. For each 1≤𝑖≤𝑛1≤i≤n it holds that 1≤𝑎𝑖≤𝑚1≤ai≤m.

Your task is to count the number of different arrays 𝑏b of length 𝑛n such that: 

• 1≤𝑏𝑖≤𝑚1≤bi≤m for each 1≤𝑖≤𝑛1≤i≤n, and 
• gcd(𝑏1,𝑏2,𝑏3,...,𝑏𝑖)=𝑎𝑖gcd(b1,b2,b3,...,bi)=ai for each 1≤𝑖≤𝑛1≤i≤n. 

Here gcd(𝑎1,𝑎2,…,𝑎𝑖)gcd(a1,a2,…,ai) denotes the greatest common divisor (GCD) of integers 𝑎1,𝑎2,…,𝑎𝑖a1,a2,…,ai.

Since this number can be too large, print it modulo 998244353998244353.

Input

Each test consist of multiple test cases. The first line contains a single integer 𝑡t (1≤𝑡≤1001≤t≤100) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1≤𝑛≤2⋅1051≤n≤2⋅105, 1≤𝑚≤1091≤m≤109) — the length of the array 𝑎a and the maximum possible value of the element.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤𝑚1≤ai≤m) — the elements of the array 𝑎a.

It is guaranteed that the sum of 𝑛n across all test cases doesn't exceed 2⋅1052⋅105.

Output

For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo 998244353998244353.

Example

input

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

output

3
1
0
595458194
200000000

题意： 给出一个长度为n的数组a，要求构造出一个长度也为n的数组b，满足a[i] = b中前i个数的最大公约数且b[i]小于等于m，问不同的方案数。

分析： 根据题意可以得到gcd(gcd(b[1], b[2], ..., b[i-1]), b[i]) = a[i]，也就是gcd(a[i-1], b[i]) = a[i]，那么a[i-1]%a[i]必须为0，否则无解。对于有解的情况可以在等式两边同时除以a[i]，这样问题就转化为已知c，在x属于[1, floor(m/a[i])]的范围内，求gcd(c, x) = 1的解数，这个问题可以用容斥原理解决，首先总数就是floor(m/a[i])，剔除与c不互质的就是互质的个数了，而不互质的个数求解需要先对c质因数分解，只要包含c的一个质因数那就不互质了，容斥一下即可。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
 
int a[200005];
vector<int> p;//存储所有质因子 
int temp;//暂存dfs结果 
int mx;//上限 
const int mod = 998244353;
 
void dfs(int now, int cnt, int val, int pre){//p里面选cnt个 
	if(now >= cnt){
		temp += floor(1.0*mx/val);
		return;
	}
	if(now+p.size()-pre < cnt) return;
	for(int i = pre+1; i < p.size(); i++)
		dfs(now+1, cnt, val*p[i], i);
	
}
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, m;
		scanf("%lld%lld", &n, &m);
		bool flag = false;
		for(int i = 1; i <= n; i++){
			scanf("%lld", &a[i]);
			if(i >= 2 && a[i-1]%a[i] != 0)
				flag = true;
		}
		if(flag){
			puts("0");
			continue;
		}
		int ans = 1;
		for(int i = 2; i <= n; i++){
			mx = floor(1.0*m/a[i]);
			int cpy = a[i-1]/a[i];
			p.clear();
			for(int j = 2; j*j <= cpy; j++){
				if(cpy%j == 0)
					p.push_back(j);	
				while(cpy%j == 0)
					cpy /= j;
			}
			if(cpy != 1) p.push_back(cpy);
			int rc = 0;//容斥原理
			int sig = 1;//符号 
			for(int j = 0; j < p.size(); j++){
				temp = 0;
				dfs(0, j+1, 1, -1); 
				rc = (rc+sig*temp)%mod;
				sig = -sig;	
			}
			ans = ((ans*(mx-rc))%mod+mod)%mod;		
		}
		printf("%lld\n", ans);
	} 
	return 0;
}