[ABC259E] LCM on Whiteboard 题解

FFTotoro · 2022-10-22 22:16:43 · 题解

本题显然我们可以用这种方法存储一个数：

用一个数组（可能是 std::vector 或其他的 STL 实现），每个元素是一个二元组，first 存的是底数，second 存的是指数。这样，最后我们可以统计出总共能产生多少个数，再丢到 set 里面去重一下即可。

现在我们来看看如何求这些数——可以根据最大公约数与最小公倍数的定义：

对于每个数判断它的某个质因数的次幂是不是所有中最高的，

• 如果不是最高的说明它对求出来的最小公倍数中分解的的这个质因数的次幂没有影响；

• 否则去除它外其他数的最小公倍数的这个质因数的次幂就是其他数中的分解质因数中包含这个质因数次幂的最大值。

这样，我们使用 std::map 可以很轻易地解决。

放代码：

#include<bits/stdc++.h>
#define int long long
#define map unordered_map
using namespace std;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,c=0; cin>>n;
  map<int,pair<int,int> > mp;
  vector<map<int,int> > p(n);
  set<vector<pair<int,int> > > s;
  for(int i=0;i<n;i++){
    int m; cin>>m;
    for(int j=1;j<=m;j++){
      int x,y; cin>>x>>y; p[i][x]=y;
      if(y>=min(mp[x].first,mp[x].second)){
        if(mp[x].first>mp[x].second)mp[x].second=y;
        else mp[x].first=y;
      }
    }
  }// 记录最高次幂
  for(int i=0;i<n;i++){
    vector<pair<int,int> > v;
    for(auto [f,e]:p[i])
      if(e==max(mp[f].first,mp[f].second)&&e>min(mp[f].first,mp[f].second)){
        v.push_back(make_pair(f,e-mp[f].second));
      }
    int sz=s.size();
    if(s.insert(v),s.size()>sz)c++;
  } // 求出最小公倍数并去重
  cout<<c<<endl;
  return 0;
}