Ban đầu bạn cần có kiến thức cơ bản về quy hoạch động. Và ý tưởng của mình là như thế này:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll f[20][4][6][8], sum = 0, K, limit = 0;
ll trau(int pos, int mod3, int mod5, int mod7) /// Quy hoạch động chữ số
{
if(pos > n) return (!mod3 || !mod5 || !mod7); /// Nếu 1 trong 3 đk thỏa mãn, trả về 1
ll &res = f[pos][mod3][mod5][mod7];
if(res != -1) return res;
res = 0;
int MIN = 0;
if(pos == 1) MIN = 1; /// Không có số '0' vô nghĩa
for(int i = MIN; i <= 9; i++)
{
res += trau(pos + 1, (mod3 * 10 + i) % 3, (mod5 * 10 + i) % 5, (mod7 * 10 + i) % 7);
}
return res;
}
void trace(int pos, int mod3, int mod5, int mod7, ll k) /// Tìm kq bằng quy hoạch dộng vị trí cấu hình
{
if(pos > n) return;
int MIN = 0;
if(pos == 1) MIN = 1;
for(int i = MIN; i <= 9; i++)
{
if(k > trau(pos + 1, (mod3 * 10 + i) % 3, (mod5 * 10 + i) % 5, (mod7 * 10 + i) % 7))
{
k -= trau(pos + 1, (mod3 * 10 + i) % 3, (mod5 * 10 + i) % 5, (mod7 * 10 + i) % 7);
}
else
{
cout << i;
trace(pos + 1, (mod3 * 10 + i) % 3, (mod5 * 10 + i) % 5, (mod7 * 10 + i) % 7, k);
return;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> K;
do /// Tìm số kết quả có độ dài là bao nhiêu
{
K -= limit;
memset(f, 255, sizeof(f));
n++;
limit = trau(1, 0, 0, 0);
}
while(limit < K);
trace(1, 0, 0, 0, K);
return 0;
}
