【LCM性质+唯一分解】ABC259 E - LCM on Whiteboard

╰半夏微凉° 2024-03-22 10:22 16阅读 0赞

[E - LCM on Whiteboard (atcoder.jp)][E - LCM on Whiteboard _atcoder.jp]

题意：

![511a10bc0fd34a099f5afaf247fd167c.png][]

思路：

考虑一个pij矩阵

如果第i个数变成1，即删除第i行，剩下的数的LCM会不会变，取决于第i行

如果第i行存在一个因子是一整列的唯一最大值，那么删除这一行之后剩下的数的LCM一定会变

因此考虑有多少行是这样的

再加上删除不是这样的行剩下的LCM这种情况即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=1e6+10;
    const int Inf=1e18;
    
    map<int,int> mx,cnt;
    
    vector<pair<int,int> > v[mxn];
    
    int N,m;
    int a,b;
    //int mx[mxn];//该质因子的最大指数 
    //int cnt[mxn];//该质因子该指数作为最大值的出现次数 
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++){
    		cin>>m;
    		for(int j=1;j<=m;j++){
    			cin>>a>>b;
    			v[i].push_back({a,b});
    			if(mx[a]<b) mx[a]=b,cnt[a]=1;
    			else if(mx[a]==b) cnt[a]++; 
    		}
    	}
    	int ok=0,ans=0;
    	for(int i=1;i<=N;i++){
    		int tag=0;
    		for(int j=0;j<v[i].size();j++){
    			if(mx[v[i][j].first]==v[i][j].second&&cnt[v[i][j].first]==1){
    				tag=1;
    				break;
    			}
    		}
    		if(tag) ans++;
    		else ok=1;
    	}
    	ans+=ok;
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__; 
    	while(__--)solve();return 0;
    }

[E - LCM on Whiteboard _atcoder.jp]: https://atcoder.jp/contests/abc259/tasks/abc259_e
[511a10bc0fd34a099f5afaf247fd167c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/73a018b4b85f4f62884ac3c43269854a.png