Little Keng

Description

Calculate how many 0s at the end of the value below:

1n + 2n + 3n + ... + mn

Input

There are multiple cases. For each cases, the input containing two integers m, n. (1 <= m <= 100 , 1 <= n <= 1000000)

Output

One line containing one integer indicatint the number of 0s.

Sample Input

4 3

Sample Output

2

題意：

就是求1^n+2^n+……+m^n的末尾有幾個0！

本題看是非常困難，看到資料之龐大！我首先想到用高精度來寫，但發現不可行，如果能過，也會逾時。但靜心一想這個數的末尾的0不會很多，而末尾的0主要是受個位上的數受影響！那麼我們就沒有必要把這個數算出來就直接算後幾位就可以！！

AC代碼：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
#include <string>
#include <stack>
#include <cctype>
using namespace std;

long long fun(long long a,long long p,long long m)
{
    if(p==0)
        return 1;
    long long r=a%m;
    long long k=1;
    while(p>1)
    {
        if((p&1)!=0)
        {
            k=(k*r)%m;
        }
        r=(r*r)%m;
        p>>=1;
    }
    return (r*k)%m;
}

int main()
{
    long long m,n;
    while(cin>>m>>n)
    {
        long long i;
        long long sum=0;
        for(i=1;i<=m;i++)
        {
            sum+=fun(i,n,1000000000);
        }
        long long k=0;
        while(sum)
        {
            if(sum%10!=0)
                break;
            if(sum%10==0)
                k++;
            sum/=10;
        }
        //printf("%d\n",k);
        cout<<k<<endl;
    }
    return 0;
}