对数学数字问题的一些处理(神奇的0)

浏览: 168 发布日期: 2017-12-29 分类: c

题目:神奇的0
Description
求l (l+1) (l+2) ...... r 的末尾零的个数。
Input
第一行一个整数T,表示样例组数。
每组一行,两个整数,l,r。
数据范围1 <= T <= 1000,1 <= l <= r <= 1e18。
Output
每组输出一行,一个整数,答案对100000007取模。

样例:
Sample Input
2
6 9
90 100
Sample Output
0
4

提示:样例一:6 * 7 * 8 * 9 = 3024;末尾无零,所以答案为0。

思路:判断末尾0出现的原因,因为乘积的形式,所以0出现的原因为2*5的时候才会在末尾出现0,所以要找l乘积到r之间中的2和5的因子的个数,少的就是末尾出现0的个数;但这样会让本来连一种因子都没有的数也进行循环了,从而超时了,所以通过组合的公式得到l*(l+1)....*(r-1)*r变为2*3*....*r/{2*3....*(l-1);然后每个乘积都从后面除2或者除5依次变小,然后除了之后的得到的为这个数的5或者2的个数;看代码;

新技巧:判断数的一些题目中,要考虑这个是数怎么来的,或者这一位怎么得到的;像这题的0得到的原因是2*5得到的;

代码:

#include<stdio.h>
 
int main()
{
    int T,x;
    long long l,r,s,ss,p,q,minn;
    scanf("%d",&T);
    for(x=1;x<=T;x++)
    {
        p=0;q=0;
        scanf("%lld%lld",&l,&r);
        l--;
        s=l;ss=r;
        while(ss>=2)
        {p+=ss/2;ss/=2;}
        while(s>=2)
        {p-=s/2;s/=2;}
        while(r>=5)
        {q+=r/5;r/=5;}
        while(l>=5)
        {q-=l/5;l/=5;}
        minn=p<q?p:q;
        printf("%lld\n",minn%100000007);
    }
    return 0;
}
返回顶部