Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 相当简单的 O(1) 算法！

Posted by Xz20011115 at 2019-05-15 13:25:47 on Problem 1019
```#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';
}
}```

Followed by: