【组合数学--容斥】CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) D. Count GCD

小咪咪 2024-03-22 01:34 59阅读 0赞

**大概思路想出来了，就差不会写容斥了....**

题意：

![2f7e6497bf284d539796c496ca607e36.png][]

![481d598d1d244b5fb1c26f7722760b15.png][]

思路：

这是一开始的思路：

![dd094ce09fa74a6eab1754c074e031dc.jpeg][]

推到最后就是求在区间\[1,m/a\[i+1\]中有多少k2满足以下条件，gcd(k1,k2)=1，k1是一个定值

这就是容斥原理的板子了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=998244353;
    
    int N,M;
    int a[mxn];
    
    int calc(int n,int top){
    	vector<pair<int,int> > v;
    	for(int i=2;i<=n/i;i++){
    		if(n%i==0){
    			int s=0;
    			while(n%i==0){
    				n/=i;
    				s++;
    			}
    			v.push_back({i,s});
    		}
    	}
    	if(n>1) v.push_back({n,1});
    	int res=0,m=v.size();
    	for(int x=1;x<(1<<m);x++){
    		int s=0,t=1;
    		for(int j=0;j<m;j++){
    			if((x>>j)&1){
    				if(t*v[j].first>top){
    					t=-1;
    					break;
    				}
    				t*=v[j].first;
    				s++;
    			}
    		}
    		if(t!=-1){
    			if(s%2) res=(res+top/t)%mod;
    			else res=((res-top/t)%mod+mod)%mod;
    		}
    	}
    	return ((top-res)%mod+mod)%mod;
    }
    void solve(){
    	cin>>N>>M;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=2;i<=N;i++){
    		if(a[i-1]%a[i]!=0){
    			cout<<0<<'\n';
    			return;
    		}
    	}
    	int ans=1;
    	for(int i=2;i<=N;i++){
    		if(a[i]==a[i-1]){
    			ans=ans*(M/a[i])%mod;
    		}else{
    			int t=calc(a[i-1]/a[i],M/a[i])%mod;
    			ans=ans*t%mod;
    		}
    	}
    	cout<<ans%mod<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[2f7e6497bf284d539796c496ca607e36.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/05bd7f53a13f4a278120cc76776d7f49.png
[481d598d1d244b5fb1c26f7722760b15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/3e7d220056ba458483018a6b70f3b968.png
[dd094ce09fa74a6eab1754c074e031dc.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/776053b474844c9bb6ff445479d38b86.png