AtCoder 259E LCM

题意：

以唯一分解形式给出$n$个数：
$$a_i=p_{i,1}^{e_{i,1}}{p}_{i,2}^{e_{i,2}}...p_{i,t}^{e_{i,t}}$$
现在可以将某个数改为$1$，求所有改法中，有多少个不同的$lcm(a_1,a_2,...,a_n)$

Solution:

由于涉及$lcm$，不妨将各个数改写成这样的形式
$$\begin{gathered} a_1=2^{e_{1,1}}{3}^{e_{1,2}}{5}^{e_{1,3}}.... \\ ... \\ {a}_n=2^{e_{n,1}}{3}^{e_{n,2}}{5}^{e_{n,3}}.... \end{gathered}$$
那么
lcm(a1,a2,...,an)=2max{e1,1,e2,1,...,en,1}3max{e1,2,e2,2,...,en,2}...lcm(a_{1},a_{2},...,a_{n})=2^{max\{e_{1,1},e_{2,1},...,e_{n,1}\}}3^{max\{e_{1,2},e_{2,2},...,e_{n,2}\}}... lcm(a1​,a2​,...,an​)=2max{e1,1​,e2,1​,...,en,1​}3max{e1,2​,e2,2​,...,en,2​}...
考虑删掉一个数的影响，即将某个数$a_k$设为1
$$a_k=2^0{3}^0{5}^0....$$
对于一个质数底$p_{k,i}$，如果他的幂是$n$个数里同底的唯一最高次的话，删去他才会对$lcm$有影响，如果两个数的唯一最高次的底的构成是一样的，那么对这两个数的操作是等价的，于是考虑存在多少个不同的构成的数。

由于唯一分解内，不同的构成的乘积一定不同，于是可以用他们的乘积代表他们的构成，用一个map来指示这个底的最高次

底x的最高次幂=map1[x]
底x有多少个最高次幂=tot[x]

把他们的乘积加入set后，set的大小就是答案

#include<iostream>
#include<vector>
#include<cstdlib>
#include<numeric>
#include<unistd.h>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<stack>
#include<utility>
#include<cctype>
#include<cassert>
#include<thread>
#include<bitset>
using namespace std;using ll=long long;
const int N=2e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e11+7;int n;
vector<int>p[N],e[N];
map<int,int>map1,tot;int main() {#ifdef stdjudgefreopen("in.txt","r",stdin);auto TimeFlagFirst=clock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) {int t; cin>>t;while(t--) {int pp,ee; cin>>pp>>ee;if(!map1.count(pp)) map1[pp]=ee,tot[pp]=1;else if(ee>map1[pp]) map1[pp]=ee,tot[pp]=1;else if(ee==map1[pp]) tot[pp]++;p[i].emplace_back(pp);e[i].emplace_back(ee);}}set<ll>set1;for(int i=1;i<=n;i++) {ll val=1;for(int j=0;j<p[i].size();j++) {if(e[i][j]==map1[p[i][j]]&&tot[p[i][j]]==1) val=val*p[i][j]%mod;}set1.insert(val);}cout<<set1.size()<<endl;#ifdef stdjudgefreopen("CON","r",stdin);std::cout<<std::endl<<"耗时:"<<std::clock()-TimeFlagFirst<<"ms"<<std::endl;std::cout<<std::flush;system("pause");#endifreturn 0;
}