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));
    }
}

External link:

Posted by xiaodao
Category: 日常