某島

… : "…アッカリ~ン . .. . " .. .
April 14, 2013

Google Code Jam 2013 Qualification Round

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: