http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4757
题目描述很简单,就是在给出的两个整数(m、n)范围内的任意一个数y,然后任意整数x(没有范围),组成一个新的整数xy,使(xy)%y=0;求在这个(m,n)范围内有多少个这样的y。时间是2秒(也就是说,用穷举的方法是会超时的),数据类型使用long long 型,int型提交WA)。

独辟蹊径,仔细分析了一下题目,根据整数整除的特点,首先发现在1—10之间的magic number 是1 、2 、5、10,然后推1—100,是1、2、5、10、25、50、100,再然后是100—1000,是100、125、500,1000,由此发现规律,magic number 可以被(1、2、5、25、125)整除,所以代码:

#include "stdio.h"
int main()
{
    long long m,n,i,j,sum,x[5]={1,2,5,25,125},flag=0,k;
    while(scanf("%lld%lld",&m,&n)!=EOF)
	{
        sum=k=0;
        flag=1;
        for(i=1;i<=11;i++)
		{
            for(j=0;j<5;j++)
                if(x[j]*flag>=m && x[j]*flag<=n)
				{
                    sum++;
                    //printf("%lld ",x[j]*flag);
                }
            flag*=10;
        }
        printf("%lld\n",sum);
    }
    return 0;
}
Ok了!

发表评论

电子邮件地址不会被公开。

Post Navigation