AtCoder ABC #152 : E - Flatten

不参加でした。
https://atcoder.jp/contests/abc152/tasks/abc152_e

問題

N要素の整数列Aが与えられる。
同じくN要素の整数列Bのうち、A[i]*B[i]=A[j]*B[j]を満たすものの最小値を求め、その和を答えよ。

解法

B[i]=LCM(A)/A[i]を求めればよい。
LCM(A)を直接具体的に求めようとすると破綻するので、素因数分解して各素因数の次数を求めよう。

int N;
int A[101010];
const ll mo=1000000007;
const int prime_max = 1100000;
vector<int> prime;
int NP,divp[prime_max];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cprime();
	map<int,int> M;
	
	FOR(i,N) {
		cin>>A[i];
		auto P=enumpr(A[i]);
		FORR(p,P) M[p.first]=max(M[p.first],p.second);
	}
	ll S=1;
	FORR(m,M) {
		FOR(i,m.second) S=S*m.first%mo;
	}
	ll ret=0;
	FOR(i,N) ret+=S*modpow(A[i])%mo;
	cout<<ret%mo<<endl;
	
	
	
}

まとめ

このあとCF Div1あったしね…