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;
}