挑战程序|挑战程序竞赛系列（38）（4.1模运算的世界（1））
挑战程序竞赛系列（38）：4.1模运算的世界（1）
详细代码可以fork下Github上leetcode项目，不定期更新。练习题如下：
- POJ 1150: The Last Non-zero Digit
此题推荐博文：http://www.hankcs.com/program/algorithm/poj-1150-the-last-non-zero-digit.html
更详细的解法：http://duanple.blog.163.com/blog/static/7097176720081016113033592/
数论入门推荐书籍：《初等数论及其应用》.
思路：
进行质因数分解，分解2和5，因为只有2和5的乘积才能构成10。在一个序列中：
1 2 3 4 5 6 7 8 9 10因数2的个数永远大于因数5的个数所以说，我们只需要求出多出来的2的个数即可，这些将会影响非零位数的最终结果。
2的质因数个数如何求解：
1 2 3 4 5 6 7 8 9 10可以分解为：
1 3 5 7 9 | 2 4 6 8 10
前半部分个数：0
后半部分个数：5 + f{1,2,3,4,5}没错，除了个2之后，能够得到5个质因数
该问题就变成了子问题{1,2,3,4,5}的质因数个数递归解决，复杂度O(logn)代码如下：
public int total2(int n){
if (n == 0) return 0;
return n / 2 + total2(n / 2);
}质因数5的个数如何？和2一个道理，所以有：
public int total5(int n){
if (n == 0) return 0;
return n / 5 + total5(n / 5);
}所以综合下（递归版本）：
public int fact_prime(int n, int x){
if (n == 0) return 0;
return n / x + fact_prime(n / x, x);
}【挑战程序|挑战程序竞赛系列（38）（4.1模运算的世界（1））】迭代版本：
public int fact_prime_iter(int n, int x){
int res = 0;
while (n > 0){
res += n / x;
n = n / x;
}
return res;
}接着，把所有的2和5的质因数全部排除后，剩余了什么？
1 2 3 4 5 6 7 8 9 10
1 1 3 1 1 3 7 1 9 1只剩下{1,3,7,9}了，那么为了能够计算非零位数，统计这些1，3，7，9的个数就完事了。统计蛮取巧，分成奇数列和偶数列1 3 5 7 9 | 2 4 6 8 10
前半部分的个数分别为：1:2 3:1 7:1 9:1
后半部分的个数分别为：子问题{1,2,3,4,5}子问题可以不去考虑了，前半部分怎么统计呢？
观察发现它包含有5的奇数倍项，但这奇数倍均除以5得到1,3,5,7....
所以变成了前部部分的子问题了...所以问题的关键就变成了求解1，3，7，9各自的个数了其实都不需要求，直接看出来了
当n = 10，1:1, 3:1, 7:1, 9:1
当n = 13？
1:2 3:2 7:1 9:1
因为13中有11和13个位数分别为1和3所以给定n
我们有 g(n, x) = n / 10 + (n % 10 >= x) + g(n / 5, x);
n/10: 每10个数都有一个
n%19: n的个位数可能产生一个好了，代码就出来了：
public int odd_end_with(int n, int x){
if (n == 0) return 0;
int res = n / 10;
res += (n % 10 >= x ? 1 : 0);
return res + odd_end_with(n / 5, x);
}public int end_with(int n, int x){
if (n == 0) return 0;
return end_with(n / 2, x) + odd_end_with(n, x);
}最后如何计算 N!(N?M)! ？
很简单，因为N-M完全包含N，所以直接把统计结果减掉即可，最终代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main{String INPUT = "./data/judge/201708/P1150.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}int[][] table = {
{6, 2, 4, 8},
{1, 3, 9, 7}, // 3
{1, 7, 9, 3}, // 7
{1, 9, 1, 9}, // 9
};
void solve() {
while (more()){
int N = ni();
int M = ni();
// 分解质因数 2 和 5 并且分别统计 2 和 5 的个数
int two= fact_prime(N, 2) - fact_prime_iter(N - M, 2);
int five= fact_prime(N, 5) - fact_prime_iter(N - M, 5);
int remain = two - five;
// 统计 1 3 7 9 的个数
int three= end_with(N, 3) - end_with(N - M, 3);
int seven= end_with(N, 7) - end_with(N - M, 7);
int nine= end_with(N, 9) - end_with(N - M, 9);
int ans = 1;
ans *= remain == 0 ? 1 : table[0][remain % 4];
ans *= three== 0 ? 1 : table[1][three% 4];
ans *= seven== 0 ? 1 : table[2][seven% 4];
ans *= nine== 0 ? 1 : table[3][nine% 4];
ans %= 10;
out.println(ans);
}
}public int fact_prime(int n, int x){
if (n == 0) return 0;
return n / x + fact_prime(n / x, x);
}public int fact_prime_iter(int n, int x){
int res = 0;
while (n > 0){
res += n / x;
n = n / x;
}
return res;
}public int odd_end_with(int n, int x){
if (n == 0) return 0;
int res = n / 10;
res += (n % 10 >= x ? 1 : 0);
return res + odd_end_with(n / 5, x);
}public int end_with(int n, int x){
if (n == 0) return 0;
return end_with(n / 2, x) + odd_end_with(n, x);
}FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}public boolean more(){
return in.hasNext();
}public int ni(){
return in.nextInt();
}public long nl(){
return in.nextLong();
}public double nd(){
return in.nextDouble();
}public String ns(){
return in.nextString();
}public char nc(){
return in.nextChar();
}class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}
推荐阅读
- 基于微信小程序带后端ssm接口小区物业管理平台设计
- 事件处理程序
- 20210307《挑战赛怂人胆》【能量将帅挑战赛（01）】
- 编写字典程序
- 周一（十一）
- 【挑战日更】Day6.《终身学习.10个你必须掌握的未来生存法则》摘录之三
- 参加【21天写作挑战赛】，第七期第14天，挑战感受小总结
- Java程序员阅读源码的小技巧，原来大牛都是这样读的，赶紧看看！
- 小程序有哪些低成本获客手段——案例解析
- 程序员|【高级Java架构师系统学习】毕业一年萌新的Java大厂面经，最新整理