sicily 1203 The Cubic End
summary
:
好不容易才想要刷道题，居然碰上了这么一道蛋疼的题，刚开始没看懂题（英语不好）， 去查了单词才看懂了，然后想了半天没想出来，还是去看人家的解题报告才有了一些 灵感，水到爆了，我靠！
解题思路
题目意思是，输入一个数a的字符串，而且最后一个数必然是{1, 3, 7, 9}中的一个， 求一个位数不超过数a的数b，使得b^3的尾数是a。^
显然，要得到一个数的最后一位，模10,同理，要得到最后2位，模20,..., 我居然还去搜了一下怎么得到一个数的尾数，结果找到了一篇五年级奥数的培训文章 （这不是赤裸裸地鄙视吗？？？）。
于是，我们可以从个位开始匹配，刚开始就是{1, 3, 7, 9}中的一个，然后匹配十 位，再是百位，一直到匹配完。
举个例子：对于123, 因为一个数的立方的个位是3,所以这个数的个位必然是7, 然后我们加10, 判断17的立方模100是不是23,发现不是，继续下去，一直到 47时发现满足条件，现在判断147的立方模1000是不是123,发现不是，继续下去， 一直到947时发现满足条件。
方法是这样，但是有一些效率的问题，如果先算立方再再模，必然会很慢，而且可能 会溢出，于是需要用到数论的知识:
a^3 % m = (((a * a) % m) * a) % m
在这个题中，因为a肯定比m要小，所以没必要先求模，直接相乘了（求模是很慢的）。
最后一个大问题，当到达10位数时，long long已经放不下了，会溢出。怎么解决这 个问题呢？我看网上有很多人用高精度做，写了一大堆代码，蛋疼死了！我是学了数论 之后才想起来做题的，于是刚好可以用到"快速乘法 "，不用原本的乘法，自己写一个， 在相乘的时候，不断地取模，这样就能保证不溢出了。
代码
1: #include <stdio.h>
2: #include <math.h>
3: #include <string.h>
4:
5: long long mul(long long left, long long right, long long power)
6: {
7: long long result;
8:
9: result = 0;
10: while (left >= 1) {
11: if (left & 1) {
12: result += right;
13: }
14: right <<= 1;
15: if (right > power) {
16: right %= power;
17: }
18: left >>= 1;
19: }
20: if (result > power) {
21: result %= power;
22: }
23: return result;
24: }
25:
26: long long cube(long long base, long long power)
27: {
28: return mul(mul(base, base, power), base, power);
29: }
30:
31: int main(int argc, char *argv[])
32: {
33: int c, len, i;
34: long long result, rem, power, step;
35: char str[11];
36:
37: scanf("%d", &c);
38: while (c--) {
39: scanf("%s", str);
40: len = strlen(str);
41: result = rem = str[len - 1] - '0';
42: if (result == 3) {
43: result = 7;
44: } else if (result == 7) {
45: result = 3;
46: }
47: power = 10;
48: for (i = len - 2; i >= 0; i--) {
49: rem += power * (str[i] - '0');
50: step = power;
51: power *= 10;
52: if (len == 10 && i == 0) {
53: while (cube(result, power) != rem) {
54: result += step;
55: }
56: break;
57: }
58: while (((((result * result) % power) * result) % power) != rem) {
59: result += step;
60: }
61: }
62: printf("%lld\n", result);
63: }
64:
65: return 0;
66: }