1853: [Scoi2010]幸运数字

Time Limit: 2 Sec  Memory Limit: 64 MB

Submit: 1774  Solved: 644

[][][]

Description

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。 现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

Input

输入数据是一行，包括2个数字a和b

Output

输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数

Sample Input

【样例输入1】

1 10

【样例输入2】

1234 4321

Sample Output

【样例输出1】

2

【样例输出2】

809

HINT

【数据范围】

对于30%的数据，保证1 < =a < =b < =1000000

对于100%的数据，保证1 < =a < =b < =10000000000

Source

题解：

容斥原理＋爆搜。

记得开double或unsigned long long。

1 #include
      
        2 using namespace std; 3 #define LL unsigned long long 4 LL sum,cc[2100],lc,a,b; 5 bool vis[2100]; 6 LL Gcd(LL aa,LL bb){
    if(bb==0)return aa;else return Gcd(bb,aa%bb);} 7 void DFS(LL x,LL y,LL gs,LL lcm, LL gcd,LL ii) 8 { 9     LL LCM,GCD,i;10     //if(lcm>x||lcm>y)return;11     if(lcm>x&&lcm>y)return;12     if(gs>0)13     {14         if(gs%2!=0)sum+=((LL)(y/lcm)-(LL)(x/lcm));15         else sum-=((LL)(y/lcm)-(LL)(x/lcm));16     }17     if(gs==lc+1||ii+1>lc)return;18     for(i=ii+1;i<=lc;i++)19     {20         if(vis[i]==false)21         {22             vis[i]=true;23             LCM=lcm;GCD=gcd;24             gcd=Gcd(lcm,cc[i]);lcm=(lcm*cc[i])/gcd;25             DFS(x,y,gs+1,lcm,gcd,i);26             lcm=LCM;gcd=GCD;27             vis[i]=false;28         }29     }30 }31 LL calc(LL x,LL y)32 {33     /*for(i=1;i<=lc;i++)34     {35         tot=0;36         DFS(x);37     }*/38     memset(vis,false,sizeof(vis));sum=0;39     DFS(x-1,y,0,1,1,0);40     return sum;41 }42 void dfs(LL k)43 {44     if(k>b)return;45     if(k!=0)cc[++lc]=k;46     dfs(k*10+6);47     dfs(k*10+8);48 }49 int main()50 {51     LL len,i;52     scanf("%lld %lld",&a,&b);53     memset(cc,0,sizeof(cc));lc=0;54     dfs(0);55     sort(cc+1,cc+lc+1);56     len=unique(cc+1,cc+lc+1)-(cc+1);57     for(i=1;i<=len/2;i++)swap(cc[i],cc[len-i+1]);58     lc=len;59     printf("%lld",calc(a,b));60     return 0;61 }