TopCoder SRM 683 Div1 Medium GCDLCM2

手こずったけど解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14169

問題

N個の正整数A[i]が与えられる。
(実行環境の都合上数式から生成するが、この問題の解法は生成式は依存しない)

これらの数列から２値x,yを抜き出し、GCD(x,y)とLCM(x,y)で置き換える、という作業を任意回数行えるものとする。
Aの総和の最大値を求めよ。

解法

x=p*a、y=p*b (a,bは互いに素)とすると、GCD(x,y)+LCM(x,y)=p+p*a*b=p*(a*b+1)≧x+yより、x!=yである限りは処理を繰り返す方がよい。

ここで、x,yをGCD,LCMで置き換えるとはどういうことかを考えてみる。
ある素因数pについて、xは最大p^aの約数、yはp^bの約数とする。
するとGCDはp^min(a,b)の倍数であり、LCMはp^max(a,b)の倍数であると言える。

すなわち、x,yをGCD,LCMで置き換えるということは、各素因数pの次数について、大きい方はLCMに、小さい方はGCDに移動する作業だと言える。
この点に気づくと、後は簡単。

A[i]を素因数分解したとき、素因数pの次数をFp[i]とする。
最終的な各素因数の積の和を最大化するため、素因数の次数の大きなものを数列の前方に集めよう。
そのため、Fp[i]を降順ソートする。（作業を繰り返すことはFp[i]を入れ替えることに相当するので、結果としてソートも可能である）
各pについてこのようにFp[i]をソートすると、最終的なAはA[i]=prod(p^Fp[i])となる。

ll mo=1000000007;
map<int,vector<int>> M;

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;
}
ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


class GCDLCM2 {
	public:
	int getMaximalSum(vector <int> start, vector <int> d, vector <int> cnt) {
		int N=start.size();
		int i,j;
		vector<ll> V;
		FOR(i,N) FOR(j,cnt[i]) V.push_back(start[i]+d[i]*j);
		sort(V.begin(),V.end());
		
		M.clear();
		FORR(r,V) {
			auto v=enumpr(r);
			FORR(rr,v) M[rr.first].push_back(rr.second);
		}
		
		vector<ll> VV;
		FOR(i,V.size()) VV.push_back(1);
		FORR(r,M) {
			vector<int> vv=r.second;
			sort(vv.begin(),vv.end());
			reverse(vv.begin(),vv.end());
			FOR(i,vv.size()) (VV[i]*=modpow(r.first,vv[i]))%=mo;
		}
		
		ll ret=0;
		FORR(r,VV) ret+=r;
		return ret%mo;
		
	}
}

まとめ

GCD,LCMの特性がまた一つ勉強になった。