SRM 683 div1 med: GCDLCM2
解法
まず x と y を使って操作をしたらどうなるのかを考えてみます。x と y の最大公約数を g として, x = g*x1, y = g*y1 であったとすると, 新しくつくられる 2 つの整数は g, g*x1*y1 となります。これが x+y とくらべて大きくなる条件は, x1+y1 < 1+x1*y1 i.e. (x1-1) * (y1-1) > 0 となり, x1 と y1 がどちらも 0 でない, すなわち x, y が互いに一方の約数でないことが条件になります。
このことから, 「x < y を満たす任意の 2 つの整数の組について, gcd(x, y) == x となる x が存在しない」という条件が成り立つまで, 操作を繰り返すのが絶対に得です。
このような操作を繰り返した最終状態を考えると, 結局すべての数について素因数がソートされたような形になります。あとはこれを実装すれば良いです(素因数を持つものについてだけソートすれば良いので計算量はそんなに多くならない)。
素因数分解 O(n) だと間に合わないーと思ってる人はこちらをどうぞ。
mayokoex.hatenablog.com
greedy な感じの問題だと「1 回 1 回の操作をどっちを先にやるのが得か」というのがよくあります(この問題でもその考察はすこし必要)が, 「最終的な状態はどうなっているか」を考える問題はあんまりない気がして面白かったです。
const ll MOD = 1e9+7; map<int, int> calc(int x) { map<int, int> M; for (int i = 2; i*i <= x; i++) { int cnt = 0; while (x%i == 0) { x /= i; cnt++; } if (cnt) M[i] = cnt; } if (x > 1) M[x] += 1; return M; } ll pow_mod(ll x, ll p) { if (x == 0) return 0; if (p == 0) return 1; if (p == 1) return x; if (p%2) return x*pow_mod(x, p-1)%MOD; ll tmp = pow_mod(x, p/2); return (tmp*tmp)%MOD; } class GCDLCM2 { public: int getMaximalSum(vector <int> start, vector <int> d, vector <int> cnt) { vector<int> nums; int L = start.size(); for (int i = 0; i < L; i++) { for (int j = 0; j < cnt[i]; j++) nums.push_back(start[i]+j*d[i]); } int n = nums.size(); vector<ll> vec(n, 1ll); map<int, vi> M; for (int i = 0; i < n; i++) { map<int, int> m = calc(nums[i]); for (auto p : m) { M[p.first].push_back(p.second); } } for (auto& p : M) { sort(p.second.rbegin(), p.second.rend()); int size = p.second.size(); for (int i = 0; i < size; i++) { (vec[n-1-i] *= pow_mod(p.first, p.second[i])) %= MOD; } } ll ans = 0; for (ll el : vec) (ans += el) %= MOD; return (int)ans; } };