开放原子开发者工作坊

Description

A lucky number is a number whose decimal representation contains only the digits \(4\) and \(7\). An almost lucky number is a number that is divisible by a lucky number. For example, \(14\), \(36\) and \(747\) are almost lucky, but \(2\) and \(17\) are not. Note that a number can be both lucky and almost lucky at the same time (for example, \(747\)).
You are given long longs a and b. Return the number of almost lucky numbers between \(a\) and$ \(b\) ,inclusive.

Input

Multiple test cases.
Each test cases is two number \(a\),\(b\) in a line seperated by a space.
\(a\) will be between \(1\) and \(10^{10}\), inclusive.
\(b\) will be between \(a\) and \(10^{10}\), inclusive.

Output

For each test case, output the answer in a single line.

Sample Input

1 10
14 14
1 100
1234 4321

Sample Output

3
1
39
1178

首先不难想到\([1,10^{10}]\)内的lucky number不多，我们可以枚举出来，且可以去除包含关系(即若\(a \mid b\)，\(b\)就没有存在的必要了)。这样算下来本质上有用的lucky number个数\(N\)只是\(O(10^3)\)级别。
首先答案每次区间可减性，即\([a,b]\)的答案为\([1,b]\)的答案减去\([1,a-1]\)答案。对于区间\([1,n]\)，我们显然可以用\(2^N\)的容斥原理。但是\(N\)太大，看上去\(2^N\)会TLE。但是由于LCM变化太大，当LCM比\(n\)大时候break复杂度就在期望的范围内了。但是可能需要卡卡常数（我懒得卡了）。

#include<cstdio>
#include<cstdlib>
using namespace std;

typedef long long ll;
#define maxn (10010)
ll A,B,lucky[maxn]; int tot,N; bool exist[maxn];

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

inline void dfs(ll num,int logten)
{
    if (logten > 10) return;
    if (logten) lucky[++tot] = num;
    dfs(num*10LL+4LL,logten+1); dfs(num*10LL+7LL,logten+1);
}

inline void DFS(ll range,ll &res,ll lcm,int now,int f)
{
    if (now > N) { if (lcm > 1) res += (range/lcm)*f; return; } 
    DFS(range,res,lcm,now+1,f);
    ll d = gcd(lcm,lucky[now]);
    if (lcm <= (range*d+lucky[now])/lucky[now]&&lcm/d*lucky[now]<=range)
        DFS(range,res,lcm/d*lucky[now],now+1,-f);
}

inline ll calc(ll range)
{
    ll ret = 0;
    DFS(range,ret,1,1,-1);
    return ret;
}

int main()
{
    freopen("3502.in","r",stdin);
    freopen("3502.out","w",stdout);
    dfs(0,0);
    for (int i = 1;i <= tot;++i)
        for (int j = 1;j <= tot;++j)
        {
            if (i == j) continue;
            if (!(lucky[i] % lucky[j])) exist[i] = true;
        }
    for (int i = 1;i <= tot;++i) if (!exist[i]) lucky[++N] = lucky[i];
    while (scanf("%lld %lld",&A,&B) != EOF) printf("%lld\n",calc(B)-calc(A-1));
    fclose(stdin); fclose(stdout);
    return 0;
}