2011-0095

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[zhan by ZhouYuChen]

1^n^ + 2^n^ + 3^n^ + ... + m^n^   (1 <= m <= 100 , 1 <= n <= 1000000) 

求上面结果末尾在有几个零

一种做法是认为结果最后的零不多，就在(mod 10^k^)下直接暴力出结果，直接统计末尾0的个数，在k>=9时下就可以AC了，甚至不用高精度，long long 就足够了。。。
复杂度为O(m*log(n))

分别考虑在(mod 2^k^)和(mod 5^k^)的结果，题目是要找在使两个结果都为0的情况，最大的k就是答案！

先考虑(mod 2^k^)的结果,找到最大的k使S % 2^k^==0 

n==1：S=(m+1)*m/2, 这个可以直接发现出来，对 m % 4 = 0,1,2,3分别考虑，综合起来，最大的k就是lowbit((m+1)/2)的右边0的个数

n==偶数：考虑到 奇数^n^ % 8 ==1, 而奇数总是先比偶数先加入到和里面，所以容易发现 k,,2*t,,==k,,2*t-1,,在考虑这个,k,,2^t^,,与k,,2^t+1^,,的关系，
在2** k,,2^t^,, 下,2^t+1^个数显然就是加了两次，所以k,,2^t+1^,,==k,,2^t^,,+1,
最后的结果肯定就与lowbit严重相关，最大的k就是lowbit((m+1)/2)的右边0的个数

n==奇数(非1)：找了若干规律发现了,lowbit((m+1)/2)的右边0的个数×2.

考虑(mod 5^k^)的结果,规律似乎比较复杂。。

但由于以上2的结果可以知道，最后的结果k最后<= lowbit(((63或64)+1)/2)的右边的0的个数×2 也就是10 ，所以最后不超过10个零

而5又要同时满足，所以此题的范围下 10^9^足矣

[zhan by ZhouYuChen]

1ⁿ + 2ⁿ + 3ⁿ + ... + mⁿ (1 <= m <= 100 , 1 <= n <= 1000000)

求上面结果末尾在有几个零

一种做法是认为结果最后的零不多，就在(mod 10^k)下直接暴力出结果，直接统计末尾0的个数，在k>=9时下就可以AC了，甚至不用高精度，long long 就足够了。。。

复杂度为O(m*log(n))

分别考虑在(mod 2^k)和(mod 5^k)的结果，题目是要找在使两个结果都为0的情况，最大的k就是答案！

先考虑(mod 2^k)的结果,找到最大的k使S % 2^k==0

n==1：S=(m+1)*m/2, 这个可以直接发现出来，对 m % 4 = 0,1,2,3分别考虑，综合起来，最大的k就是lowbit((m+1)/2)的右边0的个数

n==偶数：考虑到 奇数ⁿ % 8 ==1, 而奇数总是先比偶数先加入到和里面，所以容易发现 k_2*t==k_2*t-1在考虑这个,k_2^t与k_2^t+1的关系，

在2** k_2^t 下,2^t+1个数显然就是加了两次，所以k_2^t+1==k_2^t+1,

最后的结果肯定就与lowbit严重相关，最大的k就是lowbit((m+1)/2)的右边0的个数

n==奇数(非1)：找了若干规律发现了,lowbit((m+1)/2)的右边0的个数×2.

考虑(mod 5^k)的结果,规律似乎比较复杂。。

但由于以上2的结果可以知道，最后的结果k最后<= lowbit(((63或64)+1)/2)的右边的0的个数×2 也就是10 ，所以最后不超过10个零

而5又要同时满足，所以此题的范围下 10⁹足矣