Description
Philips 得到了一个计算器，这个计算器有两个整数单元，一开始，第一个单元包含数字 (1) ， 第二个单元包含数字 (0) 。 这个计算器支持一以下两种操作：
- 假设第一个单元的数字为 (a) ，第二个单元的数字为 (b) ，那么将第二个单元的数字改成 (b+1) 。
- 假设第一个单元的数字为 (a) ，第二个单元的数字为 (b) ，那么将第一个单元的数字改成 (a imes b) 。
现在 Philips 想知道，有多少个正整数 (x(lle xle r)) 满足， 存在一种方式从计算器初始状态开始，操作不超过 (p) 步之后使得第一个单元中的数字为 (x) 。
(2le l,rle 10^9) ， (1le ple 100)
Solution
显然 (ble p) ，即 (a) 不会有大于 (p) 的约数。
所以把小于 (p) 的质数全部筛出来，dfs出所有不超过 (r) 的能用这些质因数表示的数。这样的数最多有 (2944730) 个。
用 (f[i][j]) 表示第一维变成 (i) 第二维变成 (j) ，操作 (2) 的最少次数。显然第二维可以滚动掉。
把这些数全部排序（看起来很慢，但要相信评测姬的速度），然后外层枚举 (iin[2,p)) ，内层枚举 (jin[1,n]) ，如果 (i|a[j]) ，则寻找一个 (k) 使得 (i imes a[k]=a[j]) ，用 (f[k]) 更新 (f[j]) 。判断的话看一下 (a[i]) 是否大于等于 (l) 以及 (f[i]+i) 是否不超过 (p) 即可。
空间复杂度 (O(2944730)) ，时间复杂度 (O(mathrm{I don't know})) 。
#include<bits/stdc++.h>
using namespace std;
template <class T> inline void read(T &x) {
x = 0; bool flag = 0; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == 45) flag = 1;
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; if (flag) x = -x;
}
#define N 2944731
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define ll long long
int l, r, p, pri[101], cnt, n, a[N], f[N];
bool b[N];
bool notPri[101];
void getNum(int x, int k) {
a[++n] = x;
rep(j, k, cnt) if ((ll)x * pri[j] <= r) getNum(x * pri[j], j); else return;
}
int main() {
// freopen("calculetor.in", "r", stdin);
// freopen("calculetor.out", "w", stdout);
read(l), read(r), read(p);
rep(i, 2, p - 1) {
if (!notPri[i]) pri[++cnt] = i;
rep(j, 1, cnt) {
if (i * pri[j] >= p) break;
notPri[i * pri[j]] = 1;
if (!(i % pri[j])) break;
}
}
getNum(1, 1); sort(a + 1, a + 1 + n);
memset(f, 0x3f, sizeof f); f[1] = 0;
rep(i, 2, p - 1) {
int k = 1;
rep(j, 1, n) if (!(a[j] % i)) {
while (a[k] * i < a[j]) k++;
if ((f[j] = min(f[j], f[k] + 1)) + i <= p) b[j] = 1;
}
}
int ans = 0; rep(i, 1, n) if (b[i] && a[i] >= l) ans++;
printf("%d", ans);
return 0;
}