06 /
05
2022

【ABC254-Dの反省】平方数はすべての素因数が偶数乗である

2022年6月4日に開催されたAtCoder Beginner Contest 254（以下、ABC254）に参加しました。

AtCoder Beginner Contest 254 – AtCoder

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

結果は以下の通りでした。

3完（A,B,C）0WA
順位: 3237位
パフォーマンス: 827
レーティング: 801 → 803 (+2)

良かった点

0WAだったこと。

良くなかった点

D問題がACできなかった。
直近の目標は毎回D問題まで安定してACすることですので、今回は残念でした。
BとC問題が遅かった。

今回の反省では、解けなかったD問題を考え、解説ACしたコードまでを記録します。

D問題について

問題等は以下のリンクをご確認ください。

D – Together Square

atcoder.jp

わからなかった問題はかつっぱさんの動画で復習

わからなかった問題については、競プロYouTuber「かつっぱ」さんの動画でよく復習します。

ABC254-Dについても動画を投稿していただいていたので見て復習しました。

平方数はすべての素因数が偶数乗である

「平方数はすべての素因数が偶数乗である」とは、上記の動画でかつっぱさんがおっしゃったことで、これからも使えそうなのでこの記事のタイトルして覚えておこうと思います。

\(i = 2\) のとき \(j\) として当てはまる数を何個か列挙すると以下があります。

\(j = 2\) のとき \(2 \times 2 = 4\)
\(j = 8\) のとき \(2 \times 8 = 16\)
\(j = 18\) のとき \(2 \times 18 = 36\)
\(j = 32\) のとき \(2 \times 32 = 64\)

これらを素因数分解したものに置き換えてみると以下のようになります。

\(j = 2\) のとき \(2^1 \times 2^1 = 2^2\)
\(j = 8\) のとき \(2^1 \times 2^3 = 2^4\)
\(j = 18\) のとき \(2^1 \times (2^1 \times 3^2) = 2^2 \times 3^2\)
\(j = 32\) のとき \(2^1 \times 2^5 = 2^6\)

さらに少し変形させると以下のようになります。

\(j = 2\) のとき \(2^1 \times 2^1 = 2^2\)
\(j = 8\) のとき \(2^1 \times (2^1 \times 2^2) = 2^2\)
\(j = 18\) のとき \(2^1 \times (2^1 \times 3^2) = 2^2 \times 3^2\)
\(j = 32\) のとき \(2^1 \times (2^1 \times 2^4) = 2^2 \times 2^4\)

ここで「平方数はすべての素因数が偶数乗である」が登場します。
すべての素因数が偶数乗にできれば、それは平方数であるため、\(i\) や \(j\) に含まれている偶数乗の素因数（平方数）は考えなくてもいいといえます。

上記の式で言えば、

\(j = 8\) のときの (   ) 内の \(2^2\)、
\(j = 18\) のときの (   ) 内の \(3^2\)、
\(j = 32\) のときの (   ) 内の \(2^4\) は考えなくていいといえます。

すなわち、上の4つの式の\(i\) や \(j\) に含まれている平方数を取り除いて以下のように考えても差し支えありません。

\(j = 2\) のとき \(2^1 \times 2^1 = 2^2\)
\(j = 8\) のとき \(2^1 \times 2^1 = 2^2\)
\(j = 18\) のとき \(2^1 \times 2^1 = 2^2 \)
\(j = 32\) のとき \(2^1 \times 2^1 = 2^2 \)

結局、\(8,18,32\) は全部 \(2\) と考えます。

ACするには何をしたらいいの？

やっと、「じゃぁ、ACするには何をしたらいいの？」かが見えてきました。

まず、\(1\) から \(N\) について、平方数を取り除きます。
言い換えると、\(1\) から \(N\) について、全ての素因数を \(1\) 乗にします。
全ての素因数を \(1\) 乗にするには、その素因数の指数を2で割った余り（ \(mod\ 2\) )を計算すればいいです。
\(4\ (=2^2)\) 等、もともと平方数の場合は、全部 \(0\) 乗、すなわち \(1\) になります。

そうすると、\(1\) から \(N\) は\(1\) か素数の \(1\) 乗を掛けたもの（ \(2^1\) や \(2^1 \times 3^1\) 等)　のリストになります。
このリストから \(2\) 個を取り出して掛け算したものが、平方数（すべての素因数が偶数乗）になる組み合わせは、同じもの同士しかありません。
したがって、 \(1\) か素数の1乗を掛けたものの個数 \(\times\) 個数を足したものが答えとなります。

実装は自力で

今回の反省でACできたコードは以下のようになりました。

コード中の prime_factor 関数は N を素因数分解し、素因数とその個数を map で返す関数です。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

map<int, int> prime_factor(int N) {
  map<int, int> res;
  for(int i = 2; i * i <= N; i++) {
    while(N % i == 0) {
      res[i]++;
      N /= i;
    }
  }
  if(N != 1) {
    res[N] = 1;
  }
  return res;
}

int main() {
  int N;
  cin >> N;

  vector<int> cnt(N+1);

  for(int i = 1; i <= N; ++i) {
    map<int, int> mp = prime_factor(i);
    int res = 1;
    for(auto j:mp) {
      int k = j.first * (j.second % 2);
      if (k != 0) {
        res *= k;
      }
    }
    cnt[res]++;
  }

  int ans = 0;
  for(int i = 1; i <= N; ++i) {
    ans += cnt[i] * cnt[i];
  }
  cout << ans << endl;
  return 0;
}

TakahiroNakamori

ナカモリタカヒロ