---

题目描述：

Calculate how many 0s at the end of the value below:
1^n + 2^n + 3^n + … + m^n. (1 <= m <= 100 , 1 <= n <= 1000000)

题解：

猜测不会有很多的0.那么其实到最后取0也是模一个几位数的0.那么我们先模它的整数倍一定不会错. 注意要多模几个0. 1e9是不够的….. 模得多一点就需要ll的乘法了.

重点：

多模几个0用ll快速加法.

代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CLR(a) memset(a, 0, sizeof(a)) #define REP(i, a, b) for(int i = a;i < b;i++) #define REP_D(i, a, b) for(int i = a;i <= b;i++) typedef long long ll; using namespace std; const ll MOD = 10000000000000000; ll add(ll a, ll b) { ll res = a+b; if(res >= MOD) res -= MOD; return res; } ll mult(ll a, ll b)//快速加 { ll res = 0; ll tmp = a; while(b) { if(b&1) { res = add(res,tmp); } tmp = add(tmp, tmp); b >>= 1; } return res; } ll pow_mod(ll x, ll n)//快速幂 { ll res = 1; ll tmp = x%MOD; while(n) { if(n&1) { res = mult(res, tmp); } tmp = mult(tmp, tmp); n >>= 1; } return res; } ll n, m; ll calcu() { ll res = 1; for(ll i = 2;i<=m;i++) { res = (res + pow_mod(i, n))%MOD; } ll ans = 0; ll tt = res; if(res==0) { while(1) { ; } printf("0 "); } while(res%10==0) { ans++; res /= 10; } printf("%lld ", ans); } int main() { //freopen("1Ain.txt", "r", stdin); //freopen("1Aout.txt", "w", stdout); while(scanf("%I64d%I64d", &m, &n) != EOF) calcu(); return 0; }