[ABC243] G - Sqrt

[Q] https://atcoder.jp/contests/abc243/tasks/abc243_g

本番ではGまで目を通せなかったけど、見返したらいける問題。

X=10000を考えてみる。

A(10000)
= A(100) + A(99) + A(98) + ... + A(1)

もう少し分解してみる。
A(1) = A(1)
A(2) = A(1)
A(3) = A(1)
A(4) = A(2) + A(1)
A(5) = A(2) + A(1)
...
A(8) = A(2) + A(1)
A(9) = A(3) + A(2) + A(1)
...
A(100) = A(10) + A(9) + A(8) + ... + A(1)

A(1) ~ A(100)の個数は、
A(1)が100個 // 100 - 1^2 + 1
A(2)が97個 // 100 - 2^2 + 1
A(3)が92個 // 100 - 3^2 + 1
...
A(10)が1個 // 100 - 10^2 + 1
ずつあることがわかる。

A(10000) =  A(1) * (100 - 1^2 + 1)
          + A(2) * (100 - 2^2 + 1)
          + ...
          + A(10) * (100 - 10^2 + 1)

ということは、A(1) ~ A(10)の値をゴリゴリ出しておけば、求められる。

A(1) = 1
A(2) = 1
A(3) = 1
A(4) = A(2)+A(1) = 2
A(5) = 2
...
A(9) = 3
A(10) = 3
だ。

A(10000)を求めるのに、A(10)まで見ればいい。
A(X) を求めるのに、A(√√X) まで見ればいい。
A(9e18)を求めるのに、A(54772.255) まで見ればいい。

ので、手元で計算するのは54773まででいけそう。

実装

ll D[54780];

// D[54773]まで、Xを直接計算する。
void init() {
 D[1] = 1;
 ll base = 2;
 for (ll i = 2; i < 54774; ++i) {
   D[i] = D[i - 1];
   if (base * base == i) {
     D[i] += D[base];
     ++base;
   }
 }
}

int main() {
 cincout();

 init();
 ll T;
 cin >> T;
 rep(t, T) {
   ll X;
   cin >> X;
   // sqrtだと死ぬ
   X = sqrtl(X);
   ll ans = 0;
   ll cnt = 1;
   while (1) {
     ll items = X - cnt * cnt + 1;
     if (items < 0) break;
     ans += items * D[cnt];
     ++cnt;
   }
   cout << ans << endl;
 }
}

https://atcoder.jp/contests/abc243/submissions/30143517

Q. 1WAくらう？
A. sqrtだと死ぬ。

sqrt(9000000000000000000) = 3000000000
だが、
sqrt(8999999999999999999) = 3000000000
になってしまう。

sqrtl(9000000000000000000) = 3000000000
だが、
sqrtl(8999999999999999999) = 2999999999
になる。


sqrtはfloatだから、6桁までしか保証されず、3000000000(9桁)は壊れる。
sartlはdoubleだから、15桁まで保証される。