岛娘在空间上发的题解就看了看果然被骗了。还以为是数位dp。

原来是容斥啊。好吧第一道正式的题目。

这题还不错，有几个小优化，像排序之类的啦很常见。

看了一下别人的代码，学习了一下姿势。

---

http://hi.baidu.com/greencloud/item/6f564ec036a3ba2ee90f2edb

 

 这里直接把别人的代码贴过来。

 

 1 #include <iostream>

 2 #include <algorithm>

 3 #include <cstring>

 4  

 5 

using 

namespace std ;

 6  

 7 

#define rep( i , x , y ) for ( int i = x ; i <= y ; ++ i )

 8  

 9 typedef 

long 

long ll ;

10  

11 

const 

int maxn = 

5010 ;

12  

13 ll a , b , num[ maxn ] ;

14 

int cnt = 

0 ; 

15  

16 

void make( ll now ) {

17     

if ( now > b ) 

return ; 

18     num[ ++ cnt ] = now ;

19     make( now * 

10 + 

6 ) , make( now * 

10 + 

8 ) ;

20 }

21  

22 ll ans , n[ maxn ] ;

23 

int m = 

0 ; 

24  

25 ll X ;

26  

27 ll gcd( ll x , ll y ) {

28     

if ( x < y ) swap( x , y ) ;

29     ll k ;

30     

while ( y ) {

31         k = y ;

32         y = x % y ;

33         x = k ;

34     }

35     

return x ;

36 }

37  

38 

void dfs( 

int pos , 

int times , ll rec ) {

39     

if ( ! pos ) {

40         

if ( ! times ) 

return ;

41         ll ret = ( b / rec ) - ( a / rec ) ;

42         

if ( times & 

1 ) ans += ret ; 

else ans -= ret ;

43         

return ; 

44     }

45     ll temp = gcd( rec , n[ pos ] ) ;

46     

if ( rec / temp <= b / n[ pos ] ) dfs( pos - 

1 , times + 

1 , rec / temp * n[ pos ] ) ;

47     dfs( pos - 

1 , times , rec ) ;

48 }

49  

50 

int main(  ) {

51     cin >> a >> b ; 

52     make( 

6 ) , make( 

8 ) ;

53     rep( i , 

1 , cnt ) 

if ( num[ i ] ) {

54         rep( j , 

1 , cnt ) 

if ( i != j && ! ( num[ j ] % num[ i ] ) ) {

55             num[ j ] = 

0 ;

56         }

57     }

58     memset( n , 

0 , 

sizeof( n ) ) ;

59     rep( i , 

1 , cnt ) 

if ( num[ i ] ) {

60         n[ ++ m ] = num[ i ] ;

61     }

62     sort( n + 

1 , n + m + 

1 ) ;

63     -- a ;

64     ans = 

0 ;

65     dfs( m , 

0 , 

1 ) ;

66     cout << ans << endl ;

67     

return 

0 ; 

68 }