mayoko’s diary

プロコンとかいろいろ。

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;
    }
};