ARC 165

Fri, Jul 11, 2025

https://atcoder.jp/contests/arc165

A. Sum equals LCM

https://atcoder.jp/contests/arc165/tasks/arc165_a

自力 AC.

(i) $N$ が素冪のとき

$N = p^x$ とかけるが $A_i$ のいずれかは $A_i = p^x$ とせねばならず $2 \leq n$ という制約では $A_1 + \cdots + A_n = N$ は成立しない。

(ii) $N$ が素冪でないとき

$N$ に含まれる素因数のうち異なる2つを $p$, $q$ ($p < q$) とする. $A_1 = N/p$, $A_2 = N/q$ とすると

\begin{align*} N - A_1 - A_2 &= N - \frac{N}{p} - \frac{N}{q} \\ &= N \left(1 - \frac{1}{p} - \frac{1}{q}\right) \\ &\geq N \left(1 - \frac{1}{p} - \frac{1}{p}\right) \\ &= N \left(1 - \frac{2}{p}\right) \\ &= N \left( \frac{p-2}{p} \right) \\ &\geq 0 ~~~(\because p \geq 2) \end{align*}

これより、$N - A_1 - A_2$ 個の $1$ と $A_1$, $A_2$ からなる $A_i$ は与えられた条件を満たす。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int mx = 1e5;
    vll sieve(mx, 1);
    sieve[0] = sieve[1] = 0;
    rep2(i, 2, mx) {
        for (ll j = i + i; j < mx; j += i) {
            sieve[j] = 0;
        }
    }

    auto factor = [&](ll n) -> vector<pair<ll, ll>> {
        vector<pair<ll, ll>> ret;
        rep2(i, 2, mx) {
            if (n % i != 0) continue;
            ll cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            ret.push_back({i, cnt});
        }

        if (n != 1) {
            ret.push_back({n, 1});
        }
        return ret;
    };

    auto cal = [&]() -> void {
        ll N;
        cin >> N;

        auto ret = factor(N);
        yesno(ret.size() != 1);
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}