ABC 254

Fri, Jan 10, 2025

https://atcoder.jp/contests/abc254

A. Last Two Digits

https://atcoder.jp/contests/abc254/tasks/abc254_a

B. Practical Computing

https://atcoder.jp/contests/abc254/tasks/abc254_b

C. K Swap

https://atcoder.jp/contests/abc254/tasks/abc254_c

D. Together Square

https://atcoder.jp/contests/abc254/tasks/abc254_d

命題1

$i \times j \text{ が平方数} \leftrightarrow \frac{i\times j}{f(i) \times f(j)} \text{ が平方数}$

($\rightarrow$)

$i \times j$ が平方数であるから $i \times j$ は以下のようにかける。

$$ i \times j = \prod_{k} p^{2r_k}_{k} $$

ここで、$p_k$ は素数であり、$r_k$ は非負整数。 $f(i)$, $f(j)$ も平方数であるから

$$ f(i) = \prod_{k} p^{2n_{k}}_{k} $$$$ f(j) = \prod_{k} p^{2m_{k}}_{k} $$

とかける。ここで $n_k$, $m_k$ は非負整数。

よって

$$ \frac{i\times j}{f(i) \times f(j)} = \prod_{k} p^{2(r_k - n_k - m_k)}_k $$

であるから、因数が偶数となるため平方数。

$(\leftarrow)$

$\frac{i\times j}{f(i) \times f(j)}$ が平方数であるから、$\frac{i\times j}{f(i) \times f(j)} = x^2$ となるある正の整数 $x$ が存在する。同様にして $f(i) = y^2, f(j) = z^2$ とかける。ここで $y, z$ は正の整数.

$$ i \times j = \frac{i\times j}{f(i) \times f(j)} \times f(i) \times f(j) = x^2 y^2 z^2 = (xyz)^2 $$

よって $i \times j$ は平方数。

命題2

$\frac{i\times j}{f(i) \times f(j)}$ が平方数 $\leftrightarrow$ $\frac{i}{f(i)} = \frac{j}{f(j)}$.

$(\leftarrow)$

$\alpha = \frac{i}{f(i)} = \frac{j}{f(j)}$ とすると $\frac{i\times j}{f(i) \times f(j)} = \alpha^2$ より平方数

$(\rightarrow)$

背理法で証明する。すなわち、 $\frac{i}{f(i)} \neq \frac{j}{f(j)} \rightarrow \frac{i\times j}{f(i) \times f(j)}$ は平方数ではないを示す。

$f(i)$ は $i$ の約数のうち最大の平方数であるから $\frac{i}{f(i)} = \prod_{k} p_k$ とかける(冪がすべて1)。同様にして $\frac{j}{f(j)} = \prod_{l} p_l$ とかけ、 $\frac{i}{f(i)} \neq \frac{j}{f(j)}$ であるから少なくとも1つは異なる素因数を持つ。よって、 $\frac{i\times j}{f(i) \times f(j)}$ は少なくとも1つは冪が1となる素因数をから平方数ではない。背理法より $\frac{i\times j}{f(i) \times f(j)}$ が平方数 $\rightarrow$ $\frac{i}{f(i)} = \frac{j}{f(j)}$ が示された。

解説

命題1, 2 より $i/f(i)$ が同じになる数同士をかけると平方数になるから、$i = 1 \sim N$ を $i/f(i)$ の値でグルーピングして、それぞれのグループの大きさの2乗の和を取れば良い.

$O(N\sqrt{N})$ の計算量のプログラムでもとりあえず AC はした

#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, k, n) for (int i = (k); i < (n); ++i)
using namespace std;
using ll = long long;
// using P = pair<ll,ll>;
using P = pair<int, int>;
using vint = vector<int>;
using vll = vector<ll>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<ll>>;

// const ll INF = (ll)2e18+9;
const int INF = (int)2e9 + 7;
// const ll MOD = (ll)1e9+9;
template <typename T>
void chmin(T& a, T b) {
    a = min(a, b);
}
template <typename T>
void chmax(T& a, T b) {
    a = max(a, b);
}

template <typename T>
void print(vector<T> v) {
    int n = v.size();
    rep(i, n) {
        if (i == 0)
            cout << v[i];
        else
            cout << ' ' << v[i];
    }
    cout << endl;
}

void yesno(bool x) {
    puts(x ? "Yes" : "No");
}

void solve();

int main() {
    solve();
    return 0;
}

void solve() {
    ll N;
    cin >> N;
    vll sq;
    for (ll x = 1; x * x <= N; x++)
        sq.push_back(x * x);

    vll cnt(N + 1, 0);
    rep2(i, 1, N + 1) {
        ll s = 1;
        for (auto x : sq) {
            if (x <= i && i % x == 0)
                s = x;
        }
        cnt[i / s]++;
    }

    ll ans = 0;
    for (auto x : cnt)
        ans += x * x;
    cout << ans << endl;
}

解説コードの解説

https://atcoder.jp/contests/abc254/editorial/4065

解説のコードは約数列挙にエラトステネスを使っているっぽい.

https://qiita.com/drken/items/3beb679e54266f20ab63

vector<vector<int>> d(n+1); は d[x] が x の約数をすべて入れている配列. この配列の中の数字に平方数があるか調べて最大のものをメモ。最後に cnt[i/f] を increment して数を数えている

E. Small d and k

https://atcoder.jp/contests/abc254/tasks/abc254_e

F. Rectangle GCD

https://atcoder.jp/contests/abc254/tasks/abc254_f

2026/2/15 解説 AC

segment tree で解けるとわかっている状態でやったが解けなかった。

https://kenkoooo.com/atcoder/#/contest/show/76c42792-10db-491b-9486-ffc7f4f226e1?activeTab=Standings

$\gcd(x,y) = \gcd(x,y-x)$ の性質を使う。

$\gcd(A_i + B_j, A_i + B_{j+1}, \cdots, A_i + B_{j+w})$ がどうなるかを調べる。

$\gcd(A_i + B_j, A_i + B_{j+1}) = \gcd(A_i + B_j, B_{j+1} - B_j)$
$\gcd(A_i + B_{j+1}, A_i + B_{j+2}) = \gcd(A_i + B_{j+1}, B_{j+2} - B_{j+1})$
$\vdots$
$\gcd(A_i + B_{j+w-1}, A_i + B_{j+w}) = \gcd(A_i + B_{j+w-1}, B_{j+w} - B_{j+w-1})$

これより

\begin{align*} &\gcd(A_i + B_j, A_i + B_{j+1}, \cdots, A_i + B_{j+w}) \\ &= \gcd(A_i + B_j, B_{j+1} - B_j, B_{j+2} - B_{j+1}, \cdots, B_{j+w} - B_{j+w-1}) \end{align*}

同様にして

\begin{align*} &\gcd(A_i + B_j, A_{i+1} + B_j, \cdots, A_{i+h} + B_j) \\ &= \gcd(A_i + B_j, A_{i+1} - A_i, A_{i+2} - A_{i+1}, \cdots, A_{i+h} - A_{i+h-1}) \end{align*}

以上より

\begin{align*} &\gcd(A_i + B_j, \cdots, A_{i+h} + B_{j+w}) \\ &= \gcd(A_i + B_j, \\ &\qquad A_{i+1} - A_i, A_{i+2} - A_{i+1}, \cdots, A_{i+h} - A_{i+h-1}, \\ &\qquad B_{j+1} - B_j, B_{j+2} - B_{j+1}, \cdots, B_{j+w} - B_{j+w-1}) \end{align*}

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

    ll N, Q;
    cin >> N >> Q;

    vll A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];

    auto op = [](ll a, ll b) -> ll {
        return gcd(a, b);
    };

    auto e = []() -> ll {
        return 0;
    };

    segtree<ll, op, e> sega(N - 1), segb(N - 1);
    rep(i, N - 1) {
        sega.set(i, abs(A[i + 1] - A[i]));
        segb.set(i, abs(B[i + 1] - B[i]));
    }

    while (Q--) {
        ll h1, h2, w1, w2;
        cin >> h1 >> h2 >> w1 >> w2;
        h1--, h2--, w1--, w2--;

        ll ans = A[h1] + B[w1];
        ans = gcd(ans, sega.prod(h1, h2));
        ans = gcd(ans, segb.prod(w1, w2));
        cout << ans << '\n';
    }
}

G. Elevators

https://atcoder.jp/contests/abc254/tasks/abc254_g

Ex. Multiply or Divide by 2

https://atcoder.jp/contests/abc254/tasks/abc254_h