[bzoj 2393] Cirno的完美算数教室 (容斥原理+dfs剪枝)

题目描述

发现了一种数，这种数呢只含有和两种数字
现在想知道中有多少个数能被数整除
   1<L<R<10^{10}

题目分析

由于

R<10^{10}

，最大只有10位的数可以对答案造成贡献，每一位只能为2/9，所以最多有2000多个数，再加上把是之前的数的倍数的除去，最后只有900多个。考虑容斥，用被1个整除的-被2个整除的+被3个整除的…
由于此时间复杂度是，所以在dfs时剪枝就行，判断当前lcm是否大于R，同时注意lcm可能爆Longlong，还要判断小于0，否则跑不出这组数据（虽然也能过且）

考试时想到过此做法,以为剪枝效率不高过不了,就写了大暴力去写T3了…最后只有20pts

AC code

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL L, R, Ans, num[2500], tot;
bool used[2500];

void init()
{
  int Len = int(log10(R))+1;
  for(int i = 1; i <= Len; ++i)
    for(int j = 0; j < (1<<i); ++j)
    {
      LL now = 1; num[++tot] = 0;
      for(int k = 0; k < i; ++k)
        num[tot] += ((j&(1<<k)) ? 9 : 2) * now, now *= 10;
      if(num[tot] > R) { tot--; continue; }
      for(int k = 1; k < tot; ++k)
        if(num[tot] % num[k] == 0)
        { tot--; break; }
    }
}

inline LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }

inline void dfs(int now, int cf, LL tmp) //当前数的编号,容斥系数,当前lcm
{
  if(tmp > R || tmp <= 0) return;
  if(now > tot)
  {
    if(tmp == 1) return;
    Ans += cf * (R/tmp - L/tmp);
    return;
  }
  dfs(now+1, cf, tmp);
  dfs(now+1, -cf, tmp/gcd(tmp,num[now])*num[now]);
}

int main ()
{
  scanf("%lld%lld", &L, &R), --L, init(), dfs(1, -1, 1);
  printf("%lld\n", Ans);
}