Trailing Zeroes (II) LightOJ

题目链接

题意：求C(n,r)*p^q最后答案中末尾0的个数。

思路：很明显的思路是分解质因子2和5，可是C(n,r)如何分解呢。可以通过C(n,r)=n!/(n-r)!*r!。只要求出阶乘的因子个数就能得出答案。如何求出阶乘的因子个数，可以想到对于n！求p的质因子个数，在1~n中至少包含一个p的有n/p个，而至少包含两个p的有n/p*2......所以最后答案是n/p+n/p^2+n/p^3....为什么不是n/p+2*n/p^2呢，注意至少两个字。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<vector>
#include<algorithm>
#define N 2000006
#define ll long long
#define ull unsigned long long 
using namespace std;
int main()
{
    int t;
    int u=0;
    scanf("%d",&t);
    while(t--)
    {
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        ll d=__gcd(a,b);
        ll y=a*b/d;
        printf("Case %d: ",++u);
        if(c%y==0)
        {
            ll sum=c/y;
            ll r=__gcd(sum,y);
            while(r!=1)
            {
                sum*=r;
                y/=r;
                r=__gcd(sum,y);
            }
            printf("%lld",sum);
        }
        else
        printf("impossible");
        printf("
");
     }  
}