ABC 254

Fri, Jan 10, 2025

D

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 して数を数えている

ABC 254

Table of Contents

D

命題1

命題2

解説

解説コードの解説