problem1 link
令$f(x)$表示[0,x]中答案的个数。那么题目的答案为$f(b)-f(a-1)$
对于$f(x)$来说，假设$x$有$d$位数字,即$[0,d-1]$，那么可以进行动态规划，令$dp(i,s)$表示已经考虑了$[i,d-1]$位的数字，状态为$s$的方案数。状态需要五种：
0: 前面都是0
1: 前面不都是0，前高位数字小于$x$且未出现非4，7的数字
2: 前面不都是0，前高位数字等于$x$且未出现非4，7的数字
3: 前面不都是0，前高位数字小于$x$且出现非4，7的数字
4: 前面不都是0，前高位数字等于$x$且出现非4，7的数字
problem2 link
首先，只包含4和7的数字并不多。即便$a=1,b=10^{10}$，这中间的只包含的4,7的数字也只有$2^{1}+2^{2}+...+2^{10}$个。
假设预计算出这些数字存储在数组$A$中
那么从贪心的角度看，Join枚举的区间的开始一定是$A_{i}-bLen+1$,而 Brus枚举的区间一定是从$A_{j}+1$开始。
problem3 link
设$n$的$B$进制表示为$n=sum_{i=0}^{K}a_{i}B^{i},a_{i}<B$
首先，当$K$较大时$B$会很小。因此可以分为三类分别计算：
(1) $K=1$。即$n=a*B+b$。枚举$a,b$，判断$B$是否存在即可。
(2) $K=2$。即$n=a*B^{2}+b*B+c$。枚举$a,b,c$然后判断是否存在$B$。这里可以进行的一个优化是：假设枚举了$a,b$，那么对于连续枚举的两个c，比如$c_{1},c_{2},c_{1}<c_{2}$来说，假如$a*B_{1}^{2}+b*B_{1}+c_{1}=n,a*B_{2}^{2}+b*B_{2}+c_{2}=n$,那么$B_{1}>B_{2}$。所以如果$a*B_{1}^{2}+b*B_{1}+c_{2}<n $,那么对于$(a,b,c_{2})$来说，必然没有对应的$B$的解
(3) $K ge 3$。直接枚举$B$，判断得到的$a_{i}$是否都是lucky-number即可。
（这一道python跑不过，用了Java）
code for problem1
class TheAlmostLuckyNumbersDivOne:
def find(self, a, b):
return self.calculate(b) - self.calculate(a - 1)
def calculate(self, a):
print a
if a == 0:
return 1
d = []
while a != 0:
d.append(a % 10)
a /= 10
n = len(d)
f = self.newArray2D(n, 5, 0)
for i in range(d[n - 1] + 1):
if i == 0:
f[n - 1][0] += 1
elif i == d[n - 1]:
if i == 4 or i == 7:
f[n - 1][2] += 1
else:
f[n - 1][4] += 1
else:
if i == 4 or i == 7:
f[n - 1][1] += 1
else:
f[n - 1][3] += 1
for i in range(n - 2, -1, -1):
t = d[i]
for j in range(10):
if j == 0:
f[i][0] += f[i + 1][0]
f[i][3] += f[i + 1][1]
if j == t:
f[i][4] += f[i + 1][2]
elif j < t:
f[i][3] += f[i + 1][2]
elif j == 4 or j == 7:
f[i][1] += f[i + 1][0]
f[i][1] += f[i + 1][1]
if j == t:
f[i][2] += f[i + 1][2]
f[i][4] += f[i + 1][4]
elif j < t:
f[i][1] += f[i + 1][2]
f[i][3] += f[i + 1][4]
f[i][3] += f[i + 1][3]
else:
f[i][3] += f[i + 1][0]
f[i][3] += f[i + 1][1]
if j == t:
f[i][4] += f[i + 1][2]
elif j < t:
f[i][3] += f[i + 1][2]
return f[0][0] + f[0][1] + f[0][2] + f[0][3] + f[0][4]
def newArray2D(self, n, m, init):
f = [0] * n
for i in range(n):
f[i] = [init] * m
return f
code for problem2
class TheLuckyGameDivOne:
f = []
fLen = 0
a = 0
b = 0
jLen = 0
bLen = 0
cache = []
def generateLuckyNumber(self, x):
if x > self.b:
return
if x >= self.a:
self.f.append(x)
self.generateLuckyNumber(x * 10 + 4)
self.generateLuckyNumber(x * 10 + 7)
def binarySearch(self, key):
if self.f[0] > key:
return 0
if self.f[self.fLen - 1] <= key:
return self.fLen
low = 0
high = self.fLen - 1
maxIndex = 0
while low <= high:
mid = (low + high) >> 1
if self.f[mid] <= key:
maxIndex = max(maxIndex, mid)
low = mid + 1
else:
high = mid - 1
return maxIndex + 1
def calculate(self, start, end):
result = self.binarySearch(start + self.bLen - 1) - self.binarySearch(start - 1)
for i in range(self.fLen):
bStart = self.f[i] + 1
bEnd = bStart + self.bLen - 1
if start <= bStart and bEnd <= end:
result = min(result, self.cache[i])
return result
def init(self):
self.cache = [0] * self.fLen
for i in range(self.fLen):
bStart = self.f[i] + 1
bEnd = bStart + self.bLen - 1
self.cache[i] = self.binarySearch(bEnd) - self.binarySearch(bStart - 1)
def find(self, a, b, jLen, bLen):
self.a = a
self.b = b
self.jLen = jLen
self.bLen = bLen
self.generateLuckyNumber(0)
self.f.sort()
if len(self.f) == 0:
return 0
self.fLen = len(self.f)
self.init()
result = 0
for i in range(self.fLen + 1):
start = a
if i < self.fLen:
start = self.f[i] - bLen + 1
end = start + jLen - 1
if a <= start and end <= b:
result = max(result, self.calculate(start, end))
return result
code for problem3
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class TheLuckyBasesDivOne {
List<Long> f = new ArrayList<>();
long n;
void generateLuckyNumber(Long x) {
if (x > n) {
return;
}
if (x > 0) {
f.add(x);
}
generateLuckyNumber(x * 10 + 4);
generateLuckyNumber(x * 10 + 7);
}
static boolean isLucky(Long x) {
if (x == 0) {
return false;
}
while (x > 0) {
if (x % 10 != 4 && x % 10 != 7) {
return false;
}
x /= 10;
}
return true;
}
long calculate4() {
long result = 0;
for (long base = 2;;++ base) {
int num = 0;
boolean tag = true;
long x = n;
while (x > 0) {
tag = tag && isLucky(x % base);
num += 1;
x /= base;
}
if (num <= 3) {
break;
}
if (tag) {
result += 1;
}
}
return result;
}
long searchMax(long a, long b, long c) {
long low = 0;
long high = (long)Math.sqrt(n) + 1;
long result = 0;
while (low <= high) {
long mid = (low + high) >> 1;
if (a <= n / mid && a * mid <= n / mid && b <= n / mid
&& a * mid * mid + b * mid + c <= n) {
result = Math.max(result, mid);
low = mid + 1;
}
else {
high = mid - 1;
}
}
return result;
}
long calculate3() {
long result = 0;
for (long a : f) {
long B0 = a + 1;
if (a > n / B0 || a * B0 > n / B0) {
break;
}
for (long b : f) {
long B1 = Math.max(B0, b + 1);
if (a > n / B1 || a * B1 > n / B1
|| b * B1 > n || a * B1 * B1 + b * B1 > n) {
break;
}
long pre = -1;
for (long c : f) {
long B2 = Math.max(B1, c + 1);
if (a > n / B2 || a * B2 > n / B2
|| b * B2 > n || a * B2 * B2 + b * B2 + c > n) {
break;
}
if (pre != -1 && a * pre * pre + b * pre + c < n) {
continue;
}
pre = searchMax(a, b, c);
if (a * pre * pre + b * pre + c == n) {
result += 1;
}
}
}
}
return result;
}
long calculate2() {
long result = 0;
for (long a : f) {
if (a * (a + 1) > n) {
break;
}
for (long b : f) {
long B = Math.max(a, b) + 1;
if (a > n / B || a * B + b > n) {
break;
}
long t = n - b;
if (t % a == 0 && t / a > a && t / a > b) {
result += 1;
}
}
}
return result;
}
public long find(long n) {
if (isLucky(n)) {
return -1;
}
this.n = n;
generateLuckyNumber(0L);
Collections.sort(f);
return calculate2() + calculate3() + calculate4();
}
}