1750D - Count GCD - CodeForces Solution

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<pair<int, int>> vpi;
typedef vector<ll> vl;
typedef vector<pair<ll, ll>> vpl;
// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 1e18 + 2;
const ld pie = 3.141592653589793238462;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define minv(a) *min_element(a.begin(), a.end())
#define maxv(a) *max_element(a.begin(), a.end())
#define acc(a,n) accumulate(a.begin(),a.end(),n)
#define inp(v) for(auto& i: v) cin>>i

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define stp(n) fixed << setprecision(n)

#define fastio                        \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);                    \
  cout.tie(NULL);
#define cases          \
  int test_cases;    \
  cin >> test_cases; \
  while (test_cases--)

bool inc(pair<ll, ll> p1, pair<ll, ll> p2)
{
  if(p1.ff < p2.ff) return true;
  if(p1.ff > p2.ff) return false;
  return p1.ss > p2.ss;
}

int nCr(int n, int r, int mod){
  if(n < r || n < 0 || r < 0) return 0;

  int dp[n+1][r+1];

  for(int i=0; i<=n; i++) for(int j=0; j<=r; j++) dp[i][j] = 0;

  for(int i=0; i<=n; i++) dp[i][0] = 1;

  for(int i=1; i<=n; i++){
    for(int j=1; j<=r; j++){
      dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
      dp[i][j] %= mod;
    }
  }

  return dp[n][r]; 
}

void lgc(vi &lg, int N){
  for(int i=2; i<N; i++) lg[i] = lg[i/2] + 1;
  return;
}

void max_sparse(vector<vector<int>> &st, int N, vi &v){
  for(int i=0; i<v.size(); i++) st[i][0] = v[i];

  for(int j = 1; j < 25; j++){
    for(int i = 0; i + (1 << j) <= N; i++){
      st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
    }
  }
  return;
}

long long binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2);
  if (b % 2) return res * res * a;
  else return res * res;
}

ll phi(ll n) {
  ll result = n;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0)
        n /= i;
      result -= result / i;
    }
  }
  if (n > 1)
    result -= result / n;
  return result;
}

vl get_factors(ll a){
  vl ans;
  for(ll i=2; i*i<=a; i++){
    if(a%i == 0) ans.pb(i);
    while(a%i == 0) a/=i;
  }
  if(a != 1) ans.pb(a);
  return ans;
}

void solve(){
  
  ll n, m, ans = 1;
  cin>>n>>m;

  vl a(n);
  inp(a);

  map<ll, vl> pf;

  vl fac = get_factors(a[0]);

  for(ll i=1; i<n; i++){
    if(a[i-1]%a[i] != 0){
      cout<<"0\n";
      return;
    }
    ll mx = 0;
    ll left = a[i-1]/a[i];

    vl uf;
    for(auto i:fac) if(left % i == 0) uf.pb(i);
    ll sz = uf.size();
    for(ll k=0; k<(1<<sz); k++){
      ll pro = 1, cnt = 0;
      for(ll j=0; j<sz; j++){
        if(k & (1<<j)){
          pro *= uf[j];
          cnt++;
        }
      }
      if(cnt%2 == 0) mx += (m/a[i]) / pro;
      else mx -= (m/a[i]) / pro;
    }

    ans *= mx;
    ans %= MOD2;
  }

  cout<<ans<<"\n";

  return;
}

int32_t main()
{
  fastio

  // #ifndef ONLINE_JUDGE               
  //   freopen("input.txt", "r", stdin);                                           
  //   freopen("output.txt", "w", stdout);  
  //   freopen("error.txt", "w", stderr);                        
  // #endif 

  // int t;
  // cin>>t;
  // for(int i=1; i<=t; i++){
  //   cout<<"Case #"<<i<<": ";
  //   solve();
  // }

  cases{
    solve();
  }

	// solve();
  
  return 0;
}