题意：
对于某数k，若数字d在1-k中出现次数恰好为k，则称k为好数。
给定d，x，求x以内，对于d而言最大的好数。k范围1e18.
题解：
打表二分即可。
但是，1e18的表是没法打出来的，只能在oeis.org上查出来
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 100000+50
#define MAXM 30000
#define ll long long
#define per(i,n,m) for(int i=n;i>=m;--i)
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define mod 1000000000 + 7
#define mian main
#define mem(a, b) memset(a, b, sizeof a)
#ifndef ONLINE_JUDGE
#define dbg(x) cout << #x << "=" << x << endl;
#else
#define dbg(x)
#endif
inline int read()
{
int x = , f = ;
char ch = getchar();
while (ch < '' || ch > '')
{
if (ch == '-')
f = -;
ch = getchar();
}
while (ch >= '' && ch <= '')
{
x = * x + ch - '';
ch = getchar();
}
return x * f;
}
inline ll readll()
{
ll x = , f = ;
char ch = getchar();
while (ch < '' || ch > '')
{
if (ch == '-')
f = -;
ch = getchar();
}
while (ch >= '' && ch <= '')
{
x = * x + ch - '';
ch = getchar();
}
return x * f;
}
ll a1[] = { ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, };
ll a2[] = { ,, , , , , , , , , , , , };
ll a3[] = { , ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};
ll a4[] = { , ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};
ll a5[] = { , , , , };
ll a6[] = { ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, };
ll a7[] = { ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, };
ll a8[] = { ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, };
ll a9[] = { , , , , , , , , };
int main()
{
int _ = read();
int cnt1 = ;
int cnt2 = , cnt3 = , cnt4 = , cnt5 = , cnt6 = , cnt7 = , cnt8 =, cnt9 = ;
while (_--)
{
int n = read();
ll x = readll();
if (n == )
{
ll pos;
for (int i = ; i < cnt1; ++i)
{
if (a1[i] <= x) pos = a1[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt2; ++i)
{
if (a2[i] <= x) pos = a2[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt3; ++i)
{
if (a3[i] <= x) pos = a3[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt4; ++i)
{
if (a4[i] <= x) pos = a4[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt5; ++i)
{
if (a5[i] <= x) pos = a5[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt6; ++i)
{
if (a6[i] <= x) pos = a6[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt7; ++i)
{
if (a7[i] <= x) pos = a7[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt8; ++i)
{
if (a8[i] <= x) pos = a8[i];
}
printf("%lld\n", pos);
}
else if (n == )
{
ll pos;
for (int i = ; i < cnt9; ++i)
{
if (a9[i] <= x) pos = a9[i];
}
printf("%lld\n", pos);
}
}
}
下面补充关于此题的一个定理证明。
好数不会超过1e11
证明：记f(d,k)为1-k中数字d出现的次数，记g(d,k)=f(d,k)-k
由于对于d=1-9 已经有g(d,1e11-1)=1e10+1
因此对于任意k>1e11 有g(d,k+1e10)-g(d,k)>=1e10（考虑数的后缀是如何组成的）
通俗来讲，在1e11以后，数字d已经比数k多太多了，d再多也追不上了
可以考虑分块，维护数字的后缀信息，以加速打表。