BNU Contest 8-28 A

BNU Contest 8-28 A

A. Magic Number

Time Limit: 2000ms
Memory Limit: 32768KB

64-bit integer IO format: %lld     Java class name: Main

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

这个题就是找找规律,把满足条件的y都给写出来  就成了这个序列 1 2 5 10 20 25 50 100 125 200 250 500 1000 1250 。。。 可以看到 从第5个数开始 ,每5个数一组,相邻两组相同组内位置的数差10倍  而 2^32最大不超过 10^9所以最多只有 45个数 ,打表就能过

代码:

/*************************************************************************
    > File Name: A.cpp
    > Author: VOID_133
    > QQ: 393952764
    > Mail: [email protected] 
    > Created Time: 2014年08月28日 星期四 12时11分17秒
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

long long arr[50];

int main(void)
{
	arr[1]=1;
	arr[2]=2;
	arr[3]=5;
	arr[4]=10;
	arr[5]=20;
	arr[6]=25;
	arr[7]=50;
	arr[8]=100;
	arr[9]=125;
	for(int i=10;i<50;i+=5)
	{
		arr[i]=arr[i-5]*10;
		arr[i+1]=arr[i-4]*10;
		arr[i+2]=arr[i-3]*10;
		arr[i+3]=arr[i-2]*10;
		arr[i+4]=arr[i-1]*10;
	}
	int m,n;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		int cnt=0;
		for(int i=1;arr[i]<=n;i++)
		{
			if(arr[i]>=m) cnt++;
		}
		printf("%dn",cnt);
	}
	return 0;

}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

3 + 2 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.