TopCoder SRM 683 Div1 500 GCDLCM2

神奇的结论题

首先，由于 $g c d (x, y) * l c m (x, y) = x * y$ ，然后有个结论小学就该知道了吧，乘积一定时，两个数差得越远和越大，所以，我们应该尽量多做这种操作。

考虑将 $x, y$ 质因数分解，设 $x = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$ ， $y = p_{1}^{b_{1}} \cdot p_{2}^{b_{2}} \dots p_{n}^{b_{n}}$ （若某个质因子不存在就让它的指数为零）。考虑gcd和lcm的本质，则 $g c d (x, y) = p_{1}^{m i n (a_{1}, b_{1})} \cdot p_{2}^{m i n (a_{2}, b_{2})} \dots p_{n}^{m i n (a_{n}, b_{n})}$ ， $l c m (x, y) = p_{1}^{m a x (a_{1}, b_{1})} \cdot p_{2}^{m a x (a_{2}, b_{2})} \dots p_{n}^{m a x (a_{n}, b_{n})}$ ，然后就可以发现，每次操作过后，指数小的往小的方向移动，指数大的往大的方向移动。

所以最终的状态，应该是所有质因子按指数从小到大的顺序排列。把每个数暴力分解，sort一波就好了…

#include <bits/stdc++.h>
#define ll long long
#define fr(i,x,y) for(int i=x;i<=y;i++)
#define rf(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const int N=100001;
const int p=1e9+7;
int n;
ll a[N];
map<ll,vector<int>> mp;

template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } 
template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; }

class GCDLCM2 {
public:
    int getMaximalSum( vector <int> start, vector <int> d, vector <int> cnt ) ;
};

void deco(ll &x){
	int s=0;
	for(ll i=2;i*i<=x;i++)
	 if (x%i==0){
	 	s=0;
	 	while(x%i==0) x/=i,s++;
	 	mp[i].push_back(s);
	 }
	if (x>1) mp[x].push_back(1),x=1;
}

ll power(ll a,int n){
	ll ans=1;
	for(ll sum=a;n;n>>=1,sum=sum*sum%p) if (n&1) ans=ans*sum%p;
	return ans;
}

int GCDLCM2::getMaximalSum(vector <int> start, vector <int> d, vector <int> cnt) {
    for(int i=0;i<start.size();i++)
     for(int j=0;j<cnt[i];j++)
      a[++n]=start[i]+1ll*j*d[i];
    //fr(i,1,n) cout<<a[i]<<' ';
    fr(i,1,n) deco(a[i]);
    for(map<ll,vector<int>>::iterator it=mp.begin();it!=mp.end();it++){
    	vector<int> v=it->second;
    	sort(v.rbegin(),v.rend());
    	for(int i=0;i<v.size();i++)
    	 a[n-i]=a[n-i]*power(it->first,v[i])%p;
    	//cout<<it->first<<' ';
    }
    ll S=0;
    //cout<<endl;
    fr(i,1,n) S=(S+a[i])%p;
    return S;
}