1779. Fibonacci Sequence MultiplicationConstraints
Time Limit: 1 secs, Memory Limit: 63.9990234375 MB
Description
Maybe all of you are familiar with Fibonacci sequence. Now you are asked to solve a special version of Fibonacci sequence: The Multiplication Version.
The Fibonacci sequence – Multiplication version is defined as followed:
F[1] = aF[2] = bF[i] = F[i-1] × F[i-2] ( for alli> 2)
Now givena,bandn, I’d like you to calculate F[n].
In case of large output, if the number of digits of F[n] is larger than 1000, you just need to output “Ooops!” instead of F[n]. So, it’s a “Limited Edition”.
Input
There are multiple test cases.
The first line is an integerT(1 ≤T≤ 50) indicating the number of test cases.
For each case, there are three integersa,bandn(1 ≤a,b,n≤ 109) in a line.
Output
Output F[n] in a line for each test case. If the number of digits of F[n] is larger than 1000, just output “Ooops!” instead of F[n].
Sample Input51 2 11 2 21 2 43 2 1013 14 520Sample Output124179707499645975396352Ooops!这是我第一次写的代码，高精度（基数为10，也就是十进制），，用时0.04s：
当n达到20的时候，除非1 1 20的情况，否则必然Ooops
#include <stdio.h>#include <string.h>int a1[3010], a2[3010], a3[3010]; char f1[11], f2[11];void ready() {//转化成数组int temp, i;memset(a1, 0, sizeof(a1));memset(a2, 0, sizeof(a2));memset(a3, 0, sizeof(a3));for (temp = (int)strlen(f1), i = 0; i < temp; i++) {a1[i] = f1[temp – 1 – i] – '0';}for (temp = (int)strlen(f2), i = 0; i < temp; i++) {a2[i] = f2[temp – 1 – i] – '0';}}void multi() {int length_a1, length_a2, max_length_a3, i, j;for (length_a1 = 3009; length_a1 > 0 && a1[length_a1] == 0; length_a1–);//判断两个乘数的长度for (length_a2 = 3009; length_a2 > 0 && a2[length_a2] == 0; length_a2–);length_a1++;length_a2++;max_length_a3 = length_a1 + length_a2;memset(a3, 0, sizeof(a3));for (i = 0; i <= length_a1; i++) {//高精度乘法for (j = 0; j <= length_a2; j++) {a3[i + j] += a1[i] * a2[j];a3[i + j + 1] += a3[i + j] / 10;a3[i + j] %= 10;}}memset(a1, 0, sizeof(a1));for (i = 0; i <= length_a2; i++) {a1[i] = a2[i];}memset(a2, 0, sizeof(a2));for (i = 0; i <= max_length_a3; i++) {a2[i] = a3[i];}}int check_length_a2() {//判断当前长度int i;for (i = 3009; i > 0 && a2[i] == 0; i–);return i + 1;}int main() {int t, temp, n, i;scanf("%d", &t);while (t–) {memset(f1, '\0', sizeof(f1));memset(f2, '\0', sizeof(f2));scanf("%s %s %d", f1, f2, &n);ready();if (n == 1) {//各种预先判断printf("%s\n", f1);continue;}if (n == 2) {printf("%s\n", f2);continue;}if (f1[0] == '1' && f1[1] == '\0' && f2[0] == '1' && f2[1] == '\0') {printf("1\n");continue;}if (n >= 20) {//当n达到20就会爆printf("Ooops!\n");continue;}n = n – 2;while (check_length_a2() <= 1000 && n–) {multi();}temp = check_length_a2();if (temp <= 1000) {for (i = temp – 1; i >= 0; i–) {printf("%d", a2[i]);}printf("\n");} else {printf("Ooops!\n");}}return 0;}
试试大基数，用了0s，注意这种做法有好多陷阱：#include <stdio.h>#include <string.h>#include <math.h>int base_index = 9;//基数为10的9次方long long unit_base = (long long)pow(10, 9);//基数大小long long unit[2500];//基数为10^9的最大长度数组long long per_base[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};//构建unit数组用到的long long a1[2500], a2[2500], a3[2500]; int length_a1, length_a2, length_f1, length_f2, ans_length;char f1[11], f2[11];int get_length(int length_f) {return length_f % 9 == 0 ? length_f / 9 : length_f / 9 + 1;}void ready() {//转化数组int i, j, k;memset(a1, 0, sizeof(a1));memset(a2, 0, sizeof(a2));memset(a3, 0, sizeof(a3));length_a1 = get_length((int)strlen(f1));length_a2 = get_length((int)strlen(f2));for (i = 0, j = (int)strlen(f1) – 1; i < length_a1; i++) {//转化为基数为10^9的进制数for (k = 0; k < 9 && j >= 0; k++) {a1[i] += per_base[k] * (f1[j–] – '0');}}for (i = 0, j = (int)strlen(f2) – 1; i < length_a2; i++) {for (k = 0; k < 9 && j >= 0; k++) {a2[i] += per_base[k] * (f2[j–] – '0');}}}void multi() {int max_length_a3, i, j;for (length_a1 = 2500 – 1; length_a1 > 0 && a1[length_a1] == 0; length_a1–);//判断两个乘数的长度for (length_a2 = 2500 – 1; length_a2 > 0 && a2[length_a2] == 0; length_a2–);length_a1++;length_a2++;max_length_a3 = length_a1 + length_a2;memset(a3, 0, sizeof(a3));for (i = 0; i <= length_a1; i++) {//高精度乘法for (j = 0; j <= length_a2; j++) {a3[i + j] += a1[i] * a2[j];a3[i + j + 1] += a3[i + j] / unit_base;a3[i + j] %= unit_base;}}memset(a1, 0, sizeof(a1));//数组转移，准备下一次的比较for (i = 0; i <= length_a2; i++) {a1[i] = a2[i];}memset(a2, 0, sizeof(a2));for (i = 0; i <= max_length_a3; i++) {a2[i] = a3[i];}}int check_length_a2() {//判断当前长度int i, k;for (i = 2500 – 1; i > 0 && a2[i] == 0; i–);for (k = 8; k >= 0; k–) {if (a2[i] >= per_base[k]) {break;}}ans_length = i + 1;return i * 9 + k + 1;}void print(int i) {//注意这里！！！！wa了我好久，必须把每一个除了最大位的数的前导零输出int k;if (a2[i] == 0) {//当等于0的时候特殊处理printf("000000000");return;}for (k = 8; k >= 0 && a2[i] != 0; k–) {if (a2[i] >= per_base[k]) {break;}}k = 8 – k;while (k–) {//输出前导零printf("0");}printf("%lld", a2[i]);}int main() {int t, temp, n, i;scanf("%d", &t);while (t–) {memset(f1, '\0', sizeof(f1));memset(f2, '\0', sizeof(f2));scanf("%s %s %d", f1, f2, &n);if (n == 1) {//各种预先判断printf("%s\n", f1);continue;}if (n == 2) {printf("%s\n", f2);continue;}if (f1[0] == '1' && f1[1] == '\0' && f2[0] == '1' && f2[1] == '\0') {printf("1\n");continue;}if (n >= 20) {//当n达到20就会爆printf("Ooops!\n");continue;}ready();n = n – 2;while (1) {temp = check_length_a2();if (!(temp <= 1000 && n–))break;multi();}if (temp <= 1000) {for (i = ans_length – 1; i >= 0; i–) {if (i != ans_length – 1) {print(i);} else {printf("%lld", a2[i]);}}printf("\n");} else {printf("Ooops!\n");}}return 0;}
别人失去了信心，他却下决心实现自己的目标。
