#include <cmath>
#include <iostream>

using namespace std;

typedef unsigned long L;
typedef unsigned short S;

S f(L i)
{
    if (i <= 9) {
        return i;
    } else if (i <= 189) {
        L j = (i + 10) / 2;
        i -= (j * 2 - 10);
        while (++i < 2) {
            j /= 10;
        }
        return j % 10;
    } else if (i <= 2889) {
        L j = (i + 110) / 3;
        i -= (j * 3 - 110);
        while (++i < 3) {
            j /= 10;
        }
        return j % 10;
    } else if (i <= 38889) {
        L j = (i + 1110) / 4;
        i -= (j * 4 - 1110);
        while (++i < 4) {
            j /= 10;
        }
        return j % 10;
    } else {
        L j = (i + 11110) / 5;
        i -= (j * 5 - 11110);
        while (++i < 5) {
            j /= 10;
        }
        return j % 10;
    }
}

S g(L i)
{
    if (i <= 45) {
        L j = sqrtl(i * 2 - 1.75) - .5;
        return f(i - (j + 1) * j / 2);
    } else if (i <= 9045) {
        L j = sqrtl(i - 21) + 4;
        return f(i - (j - 8) * j - 36);
    } else if (i <= 1395495) {
        L j = (sqrtl(i * 6 - 17985.75) + 106.5) / 3;
        return f(i - (j * 3 - 213) * j / 2 - 4887);
    } else if (i <= 189414495) {
        L j = sqrtl(i * .5 - 175385.4375) + 276.25;
        return f(i - (j * 2 - 1105) * j - 503388);
    } else {
        L j = sqrtl(i * .4 - 15263847.51) + 2220.7;
        return f(i - (j * 5 - 22207) * j / 2 - 50488389);
    }
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    L i;
    S t;

    cin >> t;
    while (t--) {
        cin >> i;
        cout << g(i) << '\n';
    }
}

• Re:相当简单的 O(1) 算法！ (2859) Xz20011115 2019-05-15 14:23:23