Submission #70267573

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
using u128 = __uint128_t;

int digits_i128(i128 v){
  if(v <= 0) return 0;
  int cnt = 0;
  while(v > 0){
    v /= 10;
    ++cnt;
  }
  return cnt;
}

long long isqrt_i128(i128 v){
  if(v <= 0) return 0;
  long double vd = (long double)v;
  long double approx = sqrt(vd);
  long long r = (long long)approx;
  if (r < 0) r = 0;
  while((i128)(r+1) * (i128)(r+1) <= v) ++r;
  while((i128)r * (i128)r > v) --r;
  return r;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;cin >> T;
  while(T--){
    long long C_ll, D_ll;
    cin >> C_ll >> D_ll;
    i128 C = (i128)C_ll;
    i128 D = (i128)D_ll;
    int Lmin = digits_i128(C + 1);
    int Lmax = digits_i128(C + D);
    long long ans = 0;
    for(int L = Lmin; L <= Lmax; ++L){
      i128 k = 1;
      for(int i=0;i<L;i++) k *= 10;
      i128 base = C * (k + 1);
      i128 lowv = base + 1;
      i128 highv = base + D;
      if (lowv > highv) continue;
      long long nlo = isqrt_i128(lowv);
      if ((i128)nlo * (i128)nlo < lowv) ++nlo;
      long long nhi = isqrt_i128(highv);
      if(nlo > nhi) continue;
      for(long long n = nlo; n <= nhi; ++n){
        i128 nsq = (i128)n * (i128)n;
        i128 x = nsq - base;
        if(x < 1 || x > D) continue;
        int dig = digits_i128(C + x);
        if(dig == L) ++ans;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

Submission Info

Judge Result