Kick Start 2022 Round A 2022 Interesting Integers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <bits/stdc++.h>
using namespace std;
vector<long long> comb(13, -1);
vector<long long> zerocomb(13,-1);
vector<long long> fact(13, 1);
void initfact() {
fact[1] = 1;
for(int i = 2; i < 13; i++)
fact[i] = fact[i-1] * i;
}
long long nCr(int n, int r) {
return fact[n]/fact[r]/fact[n-r];
}
long long zeroComb(int i) {
if(i == 1) return 1;
if(i == 0) return 0;
if(zerocomb[i] != -1) return zerocomb[i];
zerocomb[i] = 0;
for(int r = 1; r <= i; r++) {
zerocomb[i] += nCr(i,r)*pow(9,i-r);
}
return zerocomb[i];
}
long long combHelper(unordered_map<int, int>& c, int used) {
if(used == 0) return 1;
long long res = 0;
for(auto [k, v] : c) {
if(v == 0) continue;
c[k]--;
res += combHelper(c, used - 1);
c[k]++;
}
return res;
}
long long helper(vector<int>& pick, int prv, int pos) {
if(pos == pick.size()) {
long long p = 1, s = 0;
unordered_map<int, int> counter;
for(auto n : pick) {
p *= n;
s += n;
counter[n]++;
}
if(p % s == 0) {
return combHelper(counter, pick.size());
} else return 0ll;
} else {
long long res = 0;
for(int i = prv; i <= 9; i++) {
pick[pos] = i;
res += helper(pick, i,pos + 1);
}
return res;
}
}
long long getComb(int i) {
if(comb[i] != -1) return comb[i];
vector<int> p(i, 0);
comb[i] = helper(p, 1, 0) + 9 * zeroComb(i-1);
return comb[i];
}
int digitCount(long long n) {
return to_string(n).length();
}
bool verify(long long n) {
long long p = 1, s = 0;
while(n) {
int d = n % 10;
p *= d;
s += d;
n /= 10;
}
return p == 0 or p % s == 0;
}
long long helper(long long n) {
if(n == 0) return 0;
int dc = digitCount(n);
long long res = 0;
long long num = 1;
for(int i = 1; i < dc; i++) {
num *= 10;
res += getComb(i);
}
for(long long st = num; st <= n; st++) {
res += verify(st);
}
return res;
}
long long solve(long long& a, long long& b) {
return helper(b) - helper(a - 1);
}
int main() {
int t;
initfact();
cin>>t;
for(int i = 1; i <= t; i++) {
long long a,b;
cin>>a>>b;
cout<<"Case #"<<i<<": "<<solve(a,b)<<endl;
}
return 0;
}
|
