Brief description:
… 問 [L, R] 區間中有多少 迴文^2-數。。
迴文^2-數。。滿足其是完全平方數。。且其本身和平方根均為迴文數。。
(L, R <= 10^100)
Analysis:
..顯然一進來就要對 L, R 取 sqrt()。。
。。後面也都是取 sqrt() 的。。以下僅考慮迴文^2-數的平方根。
。。那麼小數據暴力一下可以發現這些數的數字都是 0,1,2,3 且出現 3 的情況只有單獨的。。。3。。
。。。這些都不是本質。。本質是所有數位和的平方和要求 < 10。。。。。 以 131 為例。。。。
131 393 131 —————— 16w61
。。。。那麼顯然這個條件是為了防止中間那個位置進位。。而不進位的話就可以保證迴文了。。。
。。於是打表就行了。。。
（ dfs() 預處理出所有 sqrt(10^100) 以內的迴文^2-數的平方根。。排序後每個詢問二分。。。。）
（。。最大數據還要高精度開平方。。）
... ..
bignum l, r;
LL res = 0;
bignum sqrt(bignum x){
bignum l = 0, r = x; while (l < r){
bignum m = (l + r + 1) / 2;
if (m*m<=x) l = m;
else r = m - 1;
}
return l;
}
VS List;
void gen(string c, int n){
n *= 2; string cc = c; RVS(cc); List.PB(c+cc);
REP(i, 3) if (n+i*i<=9) List.PB(c+char('0'+i)+cc);
}
void dfs(string c, int n){
if (n > 4 || SZ(c) > 50) return; gen(c, n);
REP(i, 3) dfs(c+char('0'+i), n+sqr(i));
}
bool cmp(const string &a, const string &b){
return SZ(a) < SZ(b) || SZ(a) == SZ(b) && a < b;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("C-large-1.in", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
List.PB("1"); List.PB("2"); List.PB("3");
dfs("1", 1); dfs("2", 4); SRT(List, cmp);
//REP(i, SZ(List)) cout << List[i] << endl;
//cout << SZ(List) <<endl;
Rush{
bignum ll, rr; cin >> ll >> rr; l = sqrt(ll), r = sqrt(rr);
if (l*l < ll) l += 1;
OT(upper_bound(ALL(List), r) - lower_bound(ALL(List), l));
}
}
