ABC387B問題の高速化

問題の概要

九九の表の中で、$X$ ではない数の総和を求めなさい、というものでした。
公式解説では $9 \times 9$ の2重ループを回す、という解法だったのですが、この九九が十万十万だったらどうでしょうか。
計算量はグリッドの縦横の長さを $N$ として $O(N^2)$ となる(公式解説より)ので、もし $1 \le N \le 10 ^ 5,1 \le X \le N^2$ だったらTLEしてしまいます。今回はこの問題を高速に解く方法を考えます。
まず、一般的な九九の表を見てみましょう。

九九の表

	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
2	2	4	6	8	10	12	14	16	18
3	3	6	9	12	15	18	21	24	27
4	4	8	12	16	20	24	28	32	36
5	5	10	15	20	25	30	35	40	45
6	6	12	18	24	30	36	42	48	56
7	7	14	21	28	35	42	49	56	63
8	8	16	24	32	40	48	56	64	72
9	9	18	27	36	45	54	63	72	81

これを見ると、対称であることが分かります。つまり、$i,j(1 \le i,j \le 9)$ の積 $ij$ は、$ji$ とも等しくなります(乗法の交換法則)。例を挙げると、$i=4,j=9$ 等です。$ij=ji=36$ となります。なので、この対称性について考えると、$9 \times 9$ ではなく、$1 \le i \le \sqrt{X}$ まで考え、$X$ と一致するかなどのカウント(以下: $cnt$ )をします。答えとして、$2025-2cnt \times N$ を出力すれば良いと思うかもしれません。
でも、この解法には実は抜け穴があります。それは、$X$ が平方数のときです。この時にこの解法を使ってしまうと、$(i,j)=(\sqrt{X},\sqrt{X})$ を二回数えてしまうので、少し改良しなければいけません。$\sqrt{X}$ 回ループすることで、$X$ が平方数か判定して、もしそうなら答えから $1$ を引いて正しい答えにすることができます。
時間計算量は $O(\sqrt{X})$ となり、$1 \le N \le 10 ^ 5,1 \le X \le N^2$ でも高速に答えを出せます。
コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
  int X;
  cin >> X;
  int ans = 2025;
  for(int i = 1; i <= 9; i++) {
    if(i * i > X) {
      break;
    }
    if(X % i == 0 && X / i <= 9) {
      ans -= 2 * X;
    }
  }
  for(int i = 1; i <= 9; i++) {
    if(i * i > X) {
      break;
    }
    if(i * i == X) {
      ans += X;
    }
  }
  cout << ans << endl;
}

もし $1 \le N \le 10^5$ ならC問題くらいの難易度だったと思います。
面白い問題でした!