充分证明我已经学傻了。把ONLINE_JUDGE打成ONLINE_JUGE还WA了若干次。然后开了个10^10的数组直接CE还想了好久是怎么回事。
10^10大概会TLE，真正的数据大概只有10^9。
做法比较简单直接容斥+剪枝，反正凑起来的几个数不会很多。
#ifndef ONLINE_JUGE
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long dint;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
const int maxa = 2048;
const dint maxn = 10000000000LL;
//const dint maxn = 100000LL;
int e, t;
dint l, r, s, a[maxa], ans;
bool g[maxa];
void pre() {
t = 0;
for (int l = 1; l <= 10; ++ l)
for (int j = 0; j < (1 << l); ++ j) {
dint v(0);
for (int k = l - 1; k >= 0; -- k)
if ((j >> k) & 1)
v = v * 10 + 9;
else
v = v * 10 + 2;
a[t ++] = v;
}
sort(a, a + t);
for (int i = 0; i < t; ++ i)
for (int j = (g[i] = 0, 0); j < i && !g[i]; ++ j)
if (a[i] % a[j] == 0)
g[i] = 1;
int nt = 0;
for (int i = 0; i < t; ++ i)
if (!g[i])
a[nt ++] = a[i];
t = nt;
}
dint gcd(dint a, dint b) {
while (b % a) {
swap(a, b);
a %= b;
}
return a;
}
void dfs(int p, int c, dint v) {
if (p >= e)
return;
dfs(p + 1, c, v);
dint g = gcd(a[p], v);
//long double pd = (long double)v * a[p] / g;
dint pd = v * a[p] / g;
if (pd <= r) {
dint vn = (dint)pd;
if (c & 1)
ans -= r / vn - (l - 1) / vn;
else
ans += r / vn - (l - 1) / vn;
dfs(p + 1, c + 1, vn);
}
}
dint sov() {
e = upper_bound(a, a + t, r) - a;
ans = 0;
dfs(0, 0, 1);
return ans;
}
int main() {
pre();
scanf(lld lld, &l, &r);
printf(lld "", sov());
}