laekov

BZOJ2393 Cirno的完美算数教室

充分证明我已经学傻了。把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());

}



评论

© laekov | Powered by LOFTER