冷静一下,本来有一天的计划,就都给这NOJ的题目给耽误了。好吧一点一点来。
先是开胃菜LeetCode 172 阶乘末尾0的个数
对于某个阶乘来说,如果末尾出现0,那么说明他有一个因子是10,而10又可以分解成2和5相乘,就是说出现10这个因子的必要条件是有5这个因子,而和5配对的2是多的用不完的(最多的因子就是2了),所以只要数数1~n这些个数里面有多少个5就好了。
class Solution { public: int getfive(int n) { if(n == 0) return 0; return getfive(n/5) + n/5; } int trailingZeroes(int n) { return getfive(n); } };
然后是NOJ1170
求n!的最后一个不是0的数字是多少。比如说5!=120,那么最后的结果就是2.
其中最麻烦的就是5的倍数了,只要带上5准没好事,因为有5就会有10,就会在末尾多一个0.所以我们不要5,把所有的5的倍数都变成1,这样在不算5的倍数的情况下得到一个最后末尾数的循环
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
1,1,2,6,4,4,4,8,4,6,06,06,02,06,04,04,04,08,04,06,06,
为了对齐,我就在前面补上0.
就得到这样一个循环(6,2,6,4,4,4,8,4,6,6),其中n=1的情况是要特判为1的。
这是不含5以及5的倍数的末尾非0数,那么也不能那么任性,真的不管那些5的倍数了,还是要管他们的。
5的倍数 5,10,15,20,25,30,35,40,45,50
去除5之后 1, 2, 3, 4, 5, 6, 7, 8, 9 ,10
然后是不是又是上面的序列得到(6,2,6,4,4,4,8,4,6,6)这样的对应关系,但是等等,不是提出来5了么,不能忽视了呀,对呀所以每提出来一个5,就需要一个2,把他的影响给去除掉。
呐,所以拿出一个2消掉5,那要保证整体数值不变呀,所以还要除以一个2,但是我们能拿到的只有最后一位数,那么就有这样的关系了
2/2 = 12/ 2 = 6 ; 4/2 = 2; 6 / 2 = 16/2 =8;8 / 2 = 4;因为最后阶乘的最后一位数都是偶数,所以有这样的关系。是不是又发现个循环(2,6,8,4)
所以呢,思路就有了,有两个任务,一个是要找出所有的数中有多少个5,这个可以用上面那一个题的方法,复杂度O(logn)。还有一个就是要算出不含5的阶乘计算最后一位数到底是多少。
比如说15! 首先如果不考虑5的倍数,那么就是 4 ,但是其中有 5,10,15啊,去除5后,就是1,2,3,那么就还是要算上3!的末尾数,也就是 6,所以最终的末尾数就是 (4 * 6)%10=4啦
中间有三个5,所以是4/2/2/2=2/2/2=6/2=8
所以可以用递归的方法计算最后的数字是多少 f(n) = f(n/5)*g(n)[g(n)是不含5的倍数末尾数,f(n)是不含5的末尾数]。
做到这两件事,答案就出来了啊
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; int g[20]={1,6,2,6,4,4,4,8,4,6,6}; const int m[4]={2,6,8,4}; const int mod = 1e7; int getfive(int x) { if(x == 0) return 0; return (getfive(x/5)+x/5) % 4; } int getf(int x) { if(x < 10) return g[x]; return (getf(x/5) * g[x % 10 == 0 ? 10 : x % 10])%10; } int main() { int n; //freopen("C:\Users\Alruddy\Desktop\NOJ1170.txt","r",stdin); while(EOF != scanf("%d", &n)) { if(n == 0 || n == 1) { printf("%d ", 1); continue; } int ans = getf(n); int po = getfive(n); //cout<<ans<< " "<<po<<endl; for(int i = 0; i < 4; i++) { if(ans == m[i]) { ans = m[(po + i) % 4]; break; } } cout<<ans<<endl; } return 0; }
欸,不容易啊,主要是这个数字实在是有点大,n最大能是50000000。
还有一个神题ZOJ1222,这个是用字符串作为输入,位数能达到。。。。我也不知道能到多少位。
不过思路还是上面的思路,找到多少个5,这个5的个数可以对4去模,因为除2也是一个循环。然后算出最后的不算5的最后末尾数字是多少,然后出结果。改变的大概就是大数的除法,不过复杂度没有改变。
数的位数log10(n),除5的最多次数也就是log5(n),复杂度(log2n),这是极好的。
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; const int N = 15000; const int p[11]={1,6,2,6,4,4,4,8,4,6,6}; const int m[4]={2,6,8,4}; char s[15000]; int getlastnum(char *s) { int n = strlen(s); int a[N]; for(int i = 0; i < n; i++) a[i] = s[n - i - 1] - '0'; if(n == 1 && a[0] < 5) { if(a[0] == 1 || a[0] == 0) return 1; return p[a[0]]; } int cnt = 0; int ans = p[a[0]]; for( ; n; n -= !a[n-1]) { int c = 0; for(int tmp = 0,i = n - 1; i >= 0; i--) { tmp = tmp * 10 + a[i]; a[i] = tmp / 5; c = (c * 10 +a[i]) % 4; tmp = tmp % 5; } cnt = (cnt + c) % 4; int tp = a[0] + a[1] * 10; tp = tp % 10 == 0 ? 10 : tp % 10; ans = ans * p[tp] % 10; } for(int i = 0; i < 4; i++) { if(m[i] == ans) { ans = m[(i + cnt)%4]; break; } } return ans; } int main() { //freopen("C:\Users\Alruddy\Desktop\ZOJ1222.txt","r",stdin); while(scanf("%s", s) != EOF) { printf("%d ", getlastnum(s)); } }