ABC254 D - Together Square 解説！

2022年6月5日 21:01

　どうも！せるたわーθ(@LaserTHETA)です！今回は2022/06/04に開催されたAtCoder Beginner Contest 254 のD問題の$${O(N\sqrt{N})}$$解を解説していきます。本稿の執筆にあたり、kyopro_friendsさんのユーザ解説やツイート
を大いに参考にしております。やることは同氏のユーザ解説と変わりませんが、中学数学風な言い換えをして解いていきたいと思います！誰か一人にでも刺さる解説であればいいな…と思っています。

アライグマ「D問題は数学なのだ！　iを平方数で割れるだけ割って残ったものが最小のjで、それに平方数を掛けたものも条件を満たすのだ」https://t.co/SAFe9ldE4a pic.twitter.com/WRRDK8nYo7
— 競技プログラミングをするフレンズ (@kyopro_friends) June 4, 2022

0.問題概要

[問題] $${N}$$以下の正整数$${(i,j)}$$の組のうち,$${i×j}$$が平方数となるものは何個あるか.

$${1{\leq}N{\leq}2×10^5}$$
$${N}$$は整数

1.問題を言い換えよう！！

$${\sqrt{a}}$$が整数$${\Leftrightarrow}$$$${a}$$は平方数

が成り立ちます。
　ですので、この問題をこのように言い換えてみましょう。

[問題改] $${N}$$以下の正整数$${(i,j)}$$の組のうち,$${\sqrt{i×j}}$$が整数となるものは何個あるか.

この形なら見覚えがある！という方もいらっしゃると思います。

2.各iに対してjの最小値を求める!

　突然ですが、ここで、次の<問>を手計算で解いてみてください。

<問>　$${\sqrt{24×k}}$$ が整数となる最小の正整数$${k}$$を求めよ.

　これは公立中学校なら3年生で学習する事項の基礎的な問題です。

<解>　$${24}$$を素因数分解すると $${2^3×3}$$である.すべての素因数が偶数乗されている状態を作ればよい.ゆえに, $${k=6}$$が最小の正整数である.

考えてみれば当たり前のことですね。$${\sqrt{24}}$$$${=}$$$${2{\sqrt{6}}}$$であり、これ以上は、根号の中の数を根号の外にくくりだすことはできません。なお、この<問>の答えは[問題改]において、$${i=24}$$のとき、条件を満たす$${j}$$のうち最小のものであるといえます。

　以上から、各$${i}$$について、条件を満たす$${j}$$のうち最小のものは次の<小問題>の答えであることがわかります。

<小問題>　$${\sqrt{i×k}}$$ が整数となる最小の正整数$${k}$$を求めよ.

では、この<小問題>をプログラムを用いて解くにはどうすればいいでしょうか。
やり方は単純。いったん$${k=i}$$としたうえで、$${k}$$を2の平方数、3の平方、…で割れるだけ割っていけばよいのです。といっても表現が抽象的すぎますね。具体例を下に載せます。

(例:$${i=24}$$の場合)
　①ひとまず、$${k=i}$$とします。
　②$${k=24}$$を2の平方数である4で、割れるだけ割っていきます。
1回だけ割ることができて、$${k=6}$$になります。
　③6は3の平方数である9より小さいです。よって$${k=6}$$で、これが条件を満たす$${j}$$の最小値です。

注意点としては
　1.ある平方数で割り切れなくなったことは、あまりが0ではなくなったことで判定する
　2.ある平方数が$${k}$$を超えた場合はその$${k}$$が<小問題>の答えである
ということですね。

この部分のコード(C++)はこちら

k=i;
for(ll p = 2; p*p <= k ; p++ ){
            while( k % (p*p) == 0){
                k /= (p*p);
            }
}

3.jの最小値に平方数をかけていく！

ここまでで、各$${i}$$について、条件を満たす$${j}$$の最小値を求められました。
ここからは、各$${i}$$について、条件を満たす$${j}$$の個数を数えていきます。

といってもやることは単純です。

$${j}$$の最小値に1の平方数、2の平方数、…をかけて、それぞれ$${N}$$を超えないかどうかを判定します。もし平方数以外をかけたら,、それは条件を満たす整数ではありませんので、平方数だけをかけていけばよいです。

$${N}$$を超えないならば、[問題改]の答えを管理する変数をインクリメントします。
$${N}$$を超えたら、その$${i}$$については探索を打ち切ります。

この部分のコード(C++)はこちら

for(ll p = 1; k*(p*p) <= n ; p++){
            ans++;
}

4.コード全体

C++での実装例です。ほとんどkyopro_friendsさんのユーザ解説のものといっしょです。

//D - Together Square
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ALL(a)  (a).begin(),(a).end()
int main(){
    ll n; cin >> n;
    ll ans = 0;
    for(ll i = 1;i <= n;i++){
        ll k = i;
        for(ll p = 2; p*p <= k ; p++ ){
            while( k % (p*p) == 0){
                k /= (p*p);
            }
        }
        for(ll p = 1; k*(p*p) <= n ; p++){
            ans++;
        }
    }
    cout << ans << endl;
}

ジャッジ結果(AC)はこちら

5.おわりに

　今回のABC - Dは私にとってかなり難しかったように感じますが、学びの多い問題だったと思います！ありがとうPCTさん！！

　ここまで読んでくださりありがとうございました。誤りや議論が不十分な点などがあればお気軽に私のTwitterアカウントのDMなどで知らせてくださると非常に助かります。

この記事が気に入ったらサポートをしてみませんか？