[POJ]1150 The Last Non-zero Digit

原题

http://poj.org/problem?id=1150

参考

https://blog.csdn.net/txl199106/article/details/40653579

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>

#define LL long long

using namespace std;



// 除了统计2,5的总因子数,还统计末尾位为3,7,9的数目

void count(LL co[], int n) {
if (n == 0) {
return;
}

for (int m = n; m > 0; m = m / 5) {// 处理1...n之间的奇数的末尾位
// 末尾位可能为1, 3, 5, 7, 9
// 1无需统计,3,7,9只要求统计出现在末位的次数
// 5需要统计作为因子出现过的次数

// 将这些奇数分为以5的倍数和非5的倍数
// 例如1,3,5,7,9,11,13...,53,55,57,59
// 分为1,3,7,9,11,13,17...,53,57,59和5*1,5*3,5*5...5*11,在for循环里每次m处以5来实现问题转换


// 先统计1...m的奇数中不含因子5的数中末尾3,7,9出现的次数
co[1] += m / 10 + ((m % 10) >= 3); // m[1] 统计3
co[3] += m / 10 + ((m % 10) >= 7); // m[1] 统计7
co[4] += m / 10 + ((m % 10) >= 9); // m[1] 统计9


// 开始问题转换(利用for循环)(其实也可像下面那样用递归)
// 将1...m的奇数中含有因子5的(5,15,25,35...)(共有(m / 10 + ((m % 10) >= 5))个),先处以因子5,转化为统计(1,3,5,7...)
co[2] += m / 10 + ((m % 10) >= 5);//统计因子5
}

// m[0] 统计2
co[0] += n / 2;// 处理1...n之间的偶数,每个先处以2,问题转换为统计1...(n/2),采用递归
count(co, n / 2);
}

int main(int argc, char const *argv[]) {
int n, m;

while (~scanf("%d%d", &n, &m)) {


if (m == 0) {
printf("1\n");
continue;
}

LL co_1[5] = {0};//依次统计2,3,5,7,9的数目
LL co_2[5] = {0};

count(co_1, n);// 统计1...n
count(co_2, n - m);// 统计1...n-m
// 统计完相减
// for (int i = 0; i < 5; ++i)
// {
// printf("%d ", co_1[i]);
// }
// printf("\n");
// for (int i = 0; i < 5; ++i)
// {
// printf("%d ", co_2[i]);
// }
// printf("\n");

int ans = 1;

int r_2[] = {6, 2, 4, 8}; // 观察发现,2^i的尾数循环出现(除了2^0尾数是1外,其余情况尾数都以6,2, 4, 8...出现)(例如 1,2,4,8,16,32,64)
int r_3[] = {1, 3, 9, 7}; // 3^i的尾数循环出现
int r_7[] = {1, 7, 9, 3}; // 7^i的尾数循环出现
int r_9[] = {1, 9}; // 9^i的尾数循环出现


ans = (ans * r_3[(co_1[1] - co_2[1]) % 4]) % 10;
ans = (ans * r_7[(co_1[3] - co_2[3]) % 4]) % 10;
ans = (ans * r_9[(co_1[4] - co_2[4]) % 2]) % 10;

if (co_1[0] - co_2[0] > co_1[2] - co_2[2]) {
// 2的数目多于5
ans = (ans * r_2[((co_1[0] - co_2[0]) - (co_1[2] - co_2[2])) % 4]) % 10;
} else if (co_1[0] - co_2[0] < co_1[2] - co_2[2]) {
// 5的数目多于2
ans = 5;// 奇数乘以5,尾数依然是5
}// 2的数目和5的数目相同时乘1,无需乘


printf("%d\n", ans);


}

return 0;
}