## Editorial for VM 09 Bài 06 - SỐ RÕ RÀNG

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
#define oo 100000000
using namespace std;
int d[1501],tr[1501],ll[1501],nm;
long long f[19][10][1501],g[19][1501],re[1501];

void init()
{
int i,j,l,x,y;
fr(i,1,1500) d[i]=-1;
d[1]=1;
frr(i,1500,2)
if (d[i]==-1)
{
x=i;
while (d[x]==-1)
{
d[x]=0; tr[0]=x; y=0;
while (x)
{
y+=(x%10)*(x%10);
x/=10;
}
x=y; tr[x]=tr[0];
}
if (d[x])
do
{
x=tr[x]; d[x]=1;
} while (x!=i);
}
fr(j,0,9)
{
f[1][j][j*j]=1;
g[i][j*j]=1;
}
fr(l,2,18)
fr(j,0,9)
fr(i,j*j,1500)
{
f[l][j][i]+=g[l-1][i-j*j];
g[l][i]+=f[l][j][i];
}
}

long long calc(long long n)
{
int i,j,l=0,a[22],s=0;
long long nn=n,res=0;
fr(i,1,nm) re[i]=0;
while (nn)
{
a[++l]=nn%10; nn/=10;
}
while (l)
{
fr(i,0,a[l]-1)
fr(j,1,nm)
if (ll[j]>=s)
re[j]+=f[l][i][ll[j]-s];
s+=a[l]*a[l];
l--;
}
fr(i,1,nm)
{
res+=re[i];
if (ll[i]==s) res++;
}
return res;
}

int main()
{
int test,i;
long long n,m,lo,hi,mi;
init();
fr(i,1,1500) if (d[i]) ll[++nm]=i;
cin >> test;
while (test--)
{
cin >> n >> m;
m+=calc(n);
lo=1; hi=oo; hi*=oo;
while (lo<=hi)
{
mi=(lo+hi)/2;
if (calc(mi)<m) lo=mi+1;
else hi=mi-1;
}
mi--;
while (mi<1 || calc(mi)<m) mi++;
cout << mi << endl;
}
return 0;
}


#include <bits/stdc++.h>

const int N = 2000;

using namespace std;

bool isClear[N], was[N];
long long f[20][2][N];
long long n, kth;
vector<int> D;

int sumSqr(int x) {
int ans = 0;
while (x > 0) {
ans += (x % 10) * (x % 10);
x /= 10;
}
return ans;
}

void initialize() {
isClear[1] = 1;
for (int i = 2; i < N; ++i) {
memset(was, 0, sizeof(was));
for (int j = i; !was[j]; j = sumSqr(j)) {
was[j] = 1;
if (j < i) {
isClear[i] = isClear[j];
break;
}
}
}
}

long long dp(int i, bool bigger, int sum) {
if (i < 0) return bigger && isClear[sum];
long long &ans = f[i][bigger][sum];
if (ans != -1 ) return ans;
ans = 0;
for (int x = (bigger ? 0 : D[i]); x <= 9; ++x)
ans += dp(i - 1, bigger | (x > D[i]), sum + x * x);
return ans;
}

void solve() {
cin >> n >> kth;
long long _n = n;
D.clear();
while (_n > 0) {
D.push_back(_n % 10);
_n /= 10;
}
D.resize(18);
memset(f, -1, sizeof(f));
long long ans = 0;
bool bigger = 0;
int sum = 0;
for (int i = 17; i >= 0; --i) {
for (int x = (bigger ? 0 : D[i]); x <= 9; ++x) {
long long now = dp(i - 1, bigger | (x > D[i]), sum + x * x);
if (kth > now) {
kth -= now;
} else {
ans = ans * 10 + x;
bigger |= x > D[i];
sum += x * x;
break;
}
}
}
cout << ans << '\n';
}

int main() {
initialize();
int nTest;
cin >> nTest;
while (nTest--) {
solve();
}
return 0;
}


#### Code mẫu của RR

//Written by RR
{$ifdef rr} {$mode objfpc}
{$inline off} {$r+,q+}
{$else} {$mode objfpc}
{$inline on} {$r-,q-}
{$endif} uses math; const FINP = ''; FOUT = ''; MAXN = 18; MAXK = 1500; isClear : array[1..MAXK] of longint=( 1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,0,1, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0, 1,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0, 0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,0, 0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1, 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0, 0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0, 0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0, 0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0, 1,0,0,1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0, 1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0, 1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0, 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0); var f1,f2 : text; m,n : int64; test : longint; f : array[0..18,0..1500,0..1] of int64; g : array[0..18,0..1500] of int64; a : array[0..18] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure initf; var i,j,now,u:longint; begin fillchar(f,sizeof(f),0); fillchar(g,sizeof(g),0); f[0,0,0]:=1; u:=a[0]; g[0,0]:=1; for i:=0 to MAXN-1 do begin for j:=0 to MAXK do begin if f[i,j,0]>0 then for now:=0 to 9 do if now<a[u] then inc(f[i+1,now*now+j,1],f[i,j,0]) else if now=a[u] then inc(f[i+1,now*now+j,0],f[i,j,0]); if f[i,j,1]>0 then for now:=0 to 9 do inc(f[i+1,now*now+j,1],f[i,j,1]); end; dec(u); if u=0 then break; end; for i:=0 to MAXN-1 do for j:=0 to MAXK do if g[i,j]>0 then for now:=0 to 9 do inc(g[i+1,now*now+j],g[i,j]); end; procedure init(n:int64); var nn:int64; begin fillchar(a,sizeof(a),0); nn:=n; while (n>0) do begin inc(a[0]); a[a[0]]:=n mod 10; n:=n div 10; end; n:=nn; end; function count(n:int64):int64; var i:longint; begin init(n); initf; result:=0; for i:=1 to MAXK do if (f[a[0],i,1]+f[a[0],i,0]>0) and (isClear[i]=1) then inc(result,f[a[0],i,1]+f[a[0],i,0]); end; procedure solve; var s,i,j,now:longint; tt,sum:int64; ok:boolean; begin tt:=count(n)+m; ok:=false; s:=0; for i:=1 to MAXN do for now:=0 to 9 do begin inc(s,now*now); sum:=0; for j:=1 to 1500 do if (isClear[j]=1) and (j>=s) then inc(sum,g[18-i,j-s]); if tt>sum then dec(tt,sum) else begin if ok then write(f2,now) else if (not ok) and (now>0) then begin write(f2,now); ok:=true; end; break; end; dec(s,now*now); end; writeln(f2); end; begin openF; read(f1,test); for test:=1 to test do begin read(f1,n,m); solve; end; closeF; end.  #### Code mẫu của ll931110 {$MODE DELPHI}
program CLEAR4;
const
input  = '';
output = '';
maxd = 20;
maxs = 81;
maxk = maxd * maxs;
var
fi,fo: text;
i,t: integer;
n,m: qword;
free: array[1..maxk] of boolean;
list: array[1..maxk] of integer;
nlist: integer;
d: array[1..maxd] of integer;
F: array[-1..9,1..maxd,0..maxk] of qword;

procedure openfile;
begin
assign(fi, input);
reset(fi);

assign(fo, output);
rewrite(fo);
end;

procedure genshappy;
var
i,ss,k,tmp: integer;
begin
fillchar(free, sizeof(free), true);
free[4] := false;

for i := 1 to maxk do if free[i] then
begin
ss := i;
repeat
k := ss;
ss := 0;

while k <> 0 do
begin
tmp := k mod 10;
ss := ss + sqr(tmp);
k := k div 10;
end;

if ss = 1 then break;
if not free[ss] then
begin
free[i] := false;
break;
end;
until false;
end;

nlist := 0;
for i := 1 to maxk do if free[i] then
begin
inc(nlist);
list[nlist] := i;
end;
end;

procedure gensnum;
var
i,j,k,fs: integer;
begin
fillchar(F, sizeof(F), 0);
for i := 0 to 9 do F[i,1,i * i] := 1;

for j := 2 to maxd do
for i := 0 to 9 do
for k := sqr(i) to j * maxs do
for fs := 0 to 9 do F[i,j,k] := F[i,j,k] + F[fs,j - 1,k - sqr(i)];
end;

function calc(k,c: integer): qword;
var
i,j,s: integer;
tmp: qword;
begin
if k = 0 then exit(0);

s := d[k];
if k > 1 then dec(s);

tmp := 0;
for i := 0 to s do
for j := 1 to nlist do
if list[j] >= c then
tmp := tmp + F[i,k,list[j] - c];

calc := tmp + calc(k - 1,c + sqr(d[k]));
end;

procedure solve;
var
k,i,j,delta,digit: integer;
count,curr,next: qword;
begin

fillchar(d, sizeof(d), 0);
k := 0;
while n > 0 do
begin
inc(k);
d[k] := n mod 10;
n := n div 10;
end;

m := m + calc(k,0);

delta := 0;
j := 0;
count := 0;
while count < m do
begin
inc(j);
for i := 1 to 9 do
for k := 1 to nlist do
count := count + F[i,j,list[k]];
end;

k := j;
fillchar(d, sizeof(d), 0);

for j := k downto 1 do
begin
digit := 0;
curr := 0;
next := 0;
while next < m do
begin
curr := next;
for k := 1 to nlist do
if list[k] >= delta then
next := next + F[digit,j,list[k] - delta];

inc(digit);
end;

m := m - curr;
dec(digit);
d[j] := digit;
delta := delta + sqr(digit);
end;
end;

procedure printresult;
var
i,k: integer;
begin
k := maxd;
while d[k] = 0 do dec(k);
for i := k downto 1 do write(fo, d[i]);
writeln(fo);
end;

procedure closefile;
begin
close(fo);
close(fi);
end;

begin
openfile;
genshappy;
gensnum;

for i := 1 to t do
begin
solve;
printresult;
end;

closefile;
end.


#### Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

bool mark[2000];
int c[20], nc;
long long result;
long long F[17][2][1500];

int sum2(int x) {
if(x < 10) return x * x;
else return (x % 10) * (x % 10) + sum2(x / 10);
}

long long go(int pos, bool isgreater, int total, long long cur, long long m) {
if(m <= 0) return 0;
if(pos == -1) {
if(mark[total] && isgreater) {
if(m == 1) result = cur;
return 1;
}
return 0;
}
long long &ret = F[pos][isgreater][total], tmp;
if(ret != -1 && ret < m) return ret;
ret = 0;
m -= tmp;
ret += tmp;
}
return ret;
}

int main() {
for(int i=1;i<2000;++i) {
int x = i;
for(int k=0;k<1000;++k) x = sum2(x);
mark[i] = (x == 1);
}
int st;
long long n, m;
cin >> st;
for(int k=0;k<st;++k) {
cin >> n >> m;
memset( c, 0, sizeof(c));
for(nc = 0; n > 0; n /= 10) c[nc++] = n % 10;
memset( F, -1, sizeof(F));
go(16, 0, 0, 0, m);
cout << result << endl;
}
return 0;
}