yukicoder : No.368 LCM of K-products

なんとかすんなり解けた。
http://yukicoder.me/problems/1048

問題

N要素の整数列A[i]が与えられる。
Aから添え字の異なるK個の要素の積からなる集合をBとする。
Bの全要素の最小公倍数を求めよ。

解法

各素因数pについて、解がどうなるかを考えてみる。
A[i]を素因数分解したとき、素因数pの指数はf(p,i)となるとする。
Bの要素のうちpの指数が最大となるのは、f(p,i)が大きい順にK個A[i]を選ぶときであり、その指数はf(p,i)の和となる。

よって、まず各A[i]を素因数分解する。
そして登場した各素因数pに対し対応する指数f(p,i)の上位K個の和をg(p)とすると、p^g(p)を掛け合わせたものが解。

int N,K;
int A[101010];
ll mo=1000000007;
map<int,vector<int>> V;

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

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>>K;
	FOR(i,N) {
		cin>>x;
		auto MM=enumpr(x);
		FORR(r,MM) V[r.first].push_back(r.second);
	}
	ll ret=1;
	FORR(r,V) {
		auto VV=r.second;
		sort(ALL(VV));
		reverse(ALL(VV));
		y=0;
		FOR(x,min(K,(int)VV.size())) y+=VV[x];
		(ret *= modpow(r.first,y))%=mo;
	}
	cout<<ret<<endl;
	
}

まとめ

幸いすんなり解けたので、Codeforcesに余裕をもって挑めそうです。