Submission #52324110

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=998244353;

ll qexp(ll b,ll p,int m){
    ll res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

ll fix(ll i){
	i%=MOD;
	if (i<0) i+=MOD;
	return i;
}


int n,k;
vector<ii> p;
int arr[200005];

int brr[1<<20]; 

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k;
	rep(x,1,n+1) cin>>arr[x];
	
	for (int x=2;x<=100000005;x++) if (k%x==0){
		int curr=0;
		while (k%x==0){
			curr++;
			k/=x;
		}
		p.pub({x,curr});
	}
	if (k!=1) p.pub({k,1});
	
	// for (auto [a,b]:p) cout<<a<<" "<<b<<endl;
	
	rep(x,1,n+1){
		bool bad=false;
		int bm=0;
		
		rep(y,0,sz(p)){
			int curr=0;
			while (arr[x]%p[y].fi==0){
				curr++;
				arr[x]/=p[y].fi;
			}
			
			if (curr>p[y].se) bad=true;
			if (curr<p[y].se) bm|=1<<y;
		}
		
		if (arr[x]>1) bad=true;
		
		if (!bad) brr[bm]++;
	}
	
	rep(b,0,20){
		rep(bm,0,1<<20) if ((bm>>b)&1) brr[bm^(1<<b)]+=brr[bm];
	}
	
	int ans=0;
	rep(x,0,1<<20){
		if (__builtin_parity(x)) ans=fix(ans-qexp(2,brr[x],MOD));
		else ans=fix(ans+qexp(2,brr[x],MOD));
	}
	
	cout<<ans<<endl;
}

Submission Info

Judge Result