天天看點

zoj 3622 Magic Number

Magic Number Time Limit: 2 Seconds       Memory Limit: 32768 KB

A positive number y is called magic number if for every positive integer x it satisfies that put y to the right of x, which will form a new integer z, z mod y = 0.

Input

The input has multiple cases, each case contains two positve integers m, n(1 <= m <= n <= 2^31-1), proceed to the end of file.

Output

For each case, output the total number of magic numbers between m and n(m, n inclusively).

Sample Input

1 1
1 10
      

Sample Output

1
4      
記num(x)為x的位數      
将y放在x右邊組成的新書newnumber= x*pow(10,num(x))+y;      
要使對所有x 有y|newnumber      
因為 y|y      
是以滿足條件等價于  對所有x  y|x*pow(10,num(x))      
因為1|x,是以隻要滿足 y|pow(10,num(x)) 即可      
容易發現 2|x,5|x      
是以x=2^p *2^q;      
枚舉p和q 使之滿足   x在輸入的[m,n]并滿足y|x*pow(10,num(x)) 即可。      
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
//const int maxn=    ;

ll st,ed;
ll a[20],b[20];//a[x]:2^x ,b[x]: 2^x;

int get(ll x)//得到x的位數
{
    ll s=10;
    for(int i=1;i;i++,s*=10)
    {
        if(x/s==0)
        {
            return i;
        }
    }
}
void pre()
{
    a[0]=1;
    for(int i=1;i<=12;i++)
    {
        a[i]=a[i-1]*2;
    }

    b[0]=1;
    for(int i=1;i<=12;i++)
    {
        b[i]=b[i-1]*5;
    }

}
bool in(ll x)
{
    return st<=x&&x<=ed;
}

bool is(ll x)
{
    int num=get(x);
    ll s=1;
    for(int i=1;i<=num;i++)
    {
        s*=10;
    }

    return s%x==0;
}
int main()
{
    pre();
   while(~scanf("%d%d",&st,&ed))
   {
       int num=get(ed);
       int ans=0;
       for(int x=0;x<=num;x++)
       {
           for(int y=0;y<=num;y++)
           {
               ll ret=a[x]*b[y];
               if(!in(ret))  continue;//不在範圍内
               if(!is(ret) ) continue;//不符合條件
               ans++;
           }
       }
       printf("%d\n",ans);
   }
   return 0;
}