soj3538 幸運數字 容斥原理應用

【題目大意】：

由6和8組成的數字都是lucky數字，其倍數也是lucky數字。

求給定區間[l,r]有多少個lucky數字。（1 <= l,r <= 10,000,000,000 ）

【分析】：

若能求出[1,n]中有多少個lucky數字，問題即解。

先求僅有6和8組成的數字，記為primLucky數，lucky數是primLucky數的若干倍，顯然有容斥原理。

Ai表示[1,n]中有多少個是primLucky[i]的倍數的數字的集合。

則由：

n|A1∪A2∪...∪Am|=∑n|Ai|1≤i≤m－∑n|Ai∩Aj|1≤i≤j≤m+∑n|Ai∩Aj∩Ak|－…+(-1）^m-1）n|A1∩A2…∩Am|1≤I,j,k≤m
寫成嵌套的形式使用dfs。

生成1到10位數的primLucky數可以：

枚舉1到10的長度，定長求primLucky

或者第i長的lucky是由第i-1長的lucky數+尾數為6或者8即可。

附代碼：

[cpp] 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
#include <ctype.h> 
#include <queue> 
 
using namespace std; 
 
typedef long long ll; 
 
const int maxn = 1 << 11 ; 
ll lucky[maxn] ; 
int len ; 
const ll INF = 100000000000000000LL ; 
 
inline ll gcd(ll a, ll b) {    return b ? gcd(b,a%b) : a ; } 
 
ll lcm(ll a,ll b) 
{ 
    if ( INF / a < b ){ return INF;} 
    ll x = gcd(a, b); 
    return a / x * b; 
} 
 
inline bool get(ll &t) 
{ 
    bool flag = 0 ; 
    char c; 
    while(!isdigit(c = getchar())&&c!='-') if( c == -1 ) break ; 
    if( c == -1 ) return 0 ; 
    if(c=='-') flag = 1 , t = 0 ; 
    else t = c ^ 48; 
    while(isdigit(c = getchar()))    t = (t << 1) + (t << 3) + (c ^ 48) ; 
    if(flag) t = -t ; 
    return 1 ; 
} 
 
ll l , r ; 
 
void init() 
{ 
    ll i , j , k , t , p , q , w ; 
    for( i = k = 0 ; i < 10 ; i++) 
    { 
        //枚舉i+1長度的68數 
        w = i + 1 ; 
        for ( j = 0 ; j < (1<<(i+1)) ; j++) 
        { 
            p = 0 ; t = j ;    q = w ; 
            while (q--) 
            { 
                p *= 10 ; 
                if( t & 1 ) p += 8 ; 
                else p += 6 ; 
                t /= 2 ; 
            } 
            lucky[k++] = p ; 
        } 
    } 
    sort(lucky,lucky+k); 
    for( i = p = 1 ; i < k ; i++)  
    { 
        for ( j = 0 ; j < p ; j++) 
        { 
            if ( lucky[i] % lucky[j] == 0 ) break ; 
        } 
        if( j == p ) lucky[p++] = lucky[i] ; 
    } 
    len = p ; 
} 
 
ll dfs(int st,ll pre,ll n) 
{ 
    ll ret = 0 ; 
    int i ; 
    for ( i = 0 ; i < st ; i++) 
    { 
        ll w = lcm(pre, lucky[i]); 
        if (w <= n) ret += n / w - dfs(i, w, n); 
    } 
    return ret; 
} 
 
ll work(ll n) 
{ 
    if( n < 6 ) return 0 ; 
    return dfs(len,1,n) ; 
} 
 
void solve() 
{ 
    printf("%lld\n",work(r)-work(l)); 
} 
 
int main() 
{ 
    init(); 
    while (get(l)) 
    { 
        get(r); 
        l--; 
        solve(); 
    } 
}