Count GCD (Codeforces 1750D)
Tags: Math, combinatorics

You are given two integers $$$n$$$ and $$$m$$$ and an array $$$a$$$ of $$$n$$$ integers. For each $$$1 \le i \le n$$$ it holds that $$$1 \le a_i \le m$$$.Your task is to count the number of different arrays $$$b$$$ of length $$$n$$$ such that:   $$$1 \le b_i \le m$$$ for each $$$1 \le i \le n$$$, and  $$$\gcd(b_1,b_2,b_3,...,b_i) = a_i$$$ for each $$$1 \le i \le n$$$. Here $$$\gcd(a_1,a_2,\dots,a_i)$$$ denotes the greatest common divisor (GCD) of integers $$$a_1,a_2,\ldots,a_i$$$.Since this number can be too large, print it modulo $$$998\,244\,353$$$.

Input: Each test consist of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 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 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the length of the array $$$a$$$ and the maximum possible value of the element.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ across all test cases doesn't exceed $$$2 \cdot 10^5$$$.

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 $$$998\,244\,353$$$.

Note: In the first test case, the possible arrays $$$b$$$ are:   $$$[4,2,1]$$$;  $$$[4,2,3]$$$;  $$$[4,2,5]$$$. In the second test case, the only array satisfying the demands is $$$[1,1]$$$.In the third test case, it can be proven no such array exists.

Sample Inputs:
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

Sample Outputs:
3
1
0
595458194
200000000

Solution (Python):
import sys, array, bisect, collections, heapq, itertools, math, functools
sys.setrecursionlimit(100000)

def _r():
    return sys.stdin.buffer.readline()

def rs():
    return _r().decode('ascii').strip()

def rn():
    return int(_r())

def rnt():
    return tuple(map(int, _r().split()))

def rnl():
    return list(rnt())

def rna():
    return array.array('q', rnt())

def pnl(l):
    print(' '.join(map(str, l)))

def prime_factors(n):
    i = 2
    factors = {}
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors[i] = factors.get(i, 0) + 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors
mod = 998244353

def _calc(m, x, pf):
    sol = base = m // x
    sign = -1
    for take in range(len(pf)):
        for c in itertools.combinations(pf, take + 1):
            mult = 1
            for ce in c:
                mult *= ce
            sol = (sol + sign * (base // mult)) % mod
        sign = -sign
    return sol

def solve(n, m, a):
    sol = 1
    for i in range(1, n):
        if a[i - 1] % a[i] != 0:
            return 0
        diff = prime_factors(a[i - 1] // a[i])
        sol = sol * _calc(m, a[i], diff.keys()) % mod
    return sol
for _ in range(rn()):
    (n, m) = rnt()
    a = rnl()
    print(solve(n, m, a))

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())
from bisect import *
from heapq import *
from collections import *
from functools import *
from itertools import *
from time import *
from random import *
from math import log, gcd, sqrt, ceil

class Prime:

    def prime_sieve(self, n):
        """"""
        flag = n % 6 == 2
        sieve = bytearray((n // 3 + flag >> 3) + 1)
        for i in range(1, int(n ** 0.5) // 3 + 1):
            if not sieve[i >> 3] >> (i & 7) & 1:
                k = 3 * i + 1 | 1
                for j in range(k * k // 3, n // 3 + flag, 2 * k):
                    sieve[j >> 3] |= 1 << (j & 7)
                for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
                    sieve[j >> 3] |= 1 << (j & 7)
        return sieve

    def prime_list(self, n):
        """"""
        res = []
        if n > 1:
            res.append(2)
        if n > 2:
            res.append(3)
        if n > 4:
            sieve = self.prime_sieve(n + 1)
            res.extend((3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not sieve[i >> 3] >> (i & 7) & 1))
        return res

    def __init__(self, n) -> None:
        self.primes = self.prime_list(n)

    def dissolve(self, num):
        """"""
        lst = []
        idx = -1
        for prime in self.primes:
            if prime > num:
                break
            if num % prime == 0:
                lst.append([prime, 0])
                idx += 1
            while num % prime == 0:
                lst[idx][1] += 1
                num //= prime
        if num != 1:
            lst.append([num, 1])
        return lst
p = Prime(10 ** 5)

def solve():
    (n, m) = MI()
    nums = LII()
    mod = 998244353
    for i in range(1, n):
        if nums[i - 1] % nums[i]:
            print(0)
            return
    res = 1
    for i in range(1, n):
        if nums[i - 1] == 1:
            res *= m
            res %= mod
        elif nums[i] == nums[i - 1]:
            res *= m // nums[i]
            res %= mod
        else:
            t = nums[i - 1] // nums[i]
            M = m // nums[i]
            divs = p.dissolve(t)
            fs = []
            for (a, b) in divs:
                fs.append(a)
            S = set()
            tot = 0
            for i in range(1, len(fs) + 1):
                for c in combinations(fs, i):
                    if c not in S:
                        S.add(c)
                    else:
                        continue
                    mul = 1
                    for item in c:
                        mul *= item
                    if i & 1:
                        tot += M // mul
                    else:
                        tot -= M // mul
                    tot %= mod
            res *= M - tot
            res %= mod
    print(res)
for _ in range(II()):
    solve()

Solution (Python):
import os
import sys
DEBUG = os.getenv('_DEBUG')
if DEBUG:
    input = open('cmake-build-debug/input.txt', 'r').readline

def main(tc):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(1, len(a)):
        if a[i - 1] % a[i]:
            print(0)
            return
    prime_factors = []
    x = a[0]
    for i in range(2, int(m ** 0.5) + 1):
        if x % i == 0:
            prime_factors.append(i)
            while x % i == 0:
                x //= i
    if x > 1:
        prime_factors.append(x)
    ans = 1
    for i in range(1, len(a)):
        pf = []
        x = a[i - 1] // a[i]
        for p in prime_factors:
            if x % p == 0:
                pf.append(p)
                while x % p == 0:
                    x //= p
        if x > 1:
            pf.append(x)
        ways = m // a[i]
        for mask in range(1, 1 << len(pf)):
            cnt = 0
            gcd = a[i]
            for j in range(len(pf)):
                if mask & 1 << j:
                    cnt += 1
                    gcd *= pf[j]
            if cnt % 2:
                ways -= m // gcd
            else:
                ways += m // gcd
        ans = ans * ways % 998244353
    print(ans)
if __name__ == '__main__':
    T = 1
    T = int(input())
    for tc in range(T):
        main(tc)