[紫书CH10] 例题10-1：巨大的斐波拉契数(fib循环节、模算术、找规律、UVa11582)

紫书题解汇总：[紫书CH0] 《算法竞赛入门经典》(第2版) 题解目录

1. 题目来源

链接：UVA11582 Colossal Fibonacci Numbers!

2. 题目说明

中文描述：

输入两个非负整数 a、b 和正整数 n$(0≤a,b <2^{64},1≤n≤1000)$(0≤a,b<264,1≤n≤1000)，你的任务是计算$f(ab)$f(ab)除以 n 的余数。其中$f(0)=f(1)=1$f(0)=f(1)=1，且对于所有非负整数 i，$f(i+2)=f(i+1)+f(i)$f(i+2)=f(i+1)+f(i)。

3. 题目解析

方法一：fib循环节+模算术+找规律

竞赛题与一般的面试笔试题的最大不同点在于它的数据范围。在 LeetCode 上大多都不会出现爆 int 的情况，即数据不够强，但是这个题目所要求的 2^64 显然已经大大超出了 int 的范围。那么 long 够吗？long long 够吗？其实，都不够…

int ：-2147483648～2147483647 (10位数，2e9 2^31 - 1)
unsigned int： 0～4294967295 (10位数，4e9)
long long：-9223372036854775808～9223372036854775807 (19位数， 9e18 ) 2^63 - 1
unsigned long long：0～18446744073709551615 (20位数，1e19) 2^64 - 1

所以在此 a、b 的数据类型得是 unsigned long long 才可以。采用 scanf、printf 读取输出时需要使用 %llu 或者 %I64u。

主要思想就是打表+fib循环节。 lrj 大佬在书中提到对 n 取模，余数最多 n 种，所以最多 n^2 种余数组合情况，也就是在 n^2 项内就会出现循环节，导致后面的进行重复。但好像用不到 n^2 那么多项，fib 取模循环节我也不太了解，甚至今天第一次知道…关键就是二维数组的大小开辟选择，不放心的话就直接 MAXN * MAXN 好点，反正找到了就会 break 掉。并且在这找的循环节还是 0、1 循环节，那要是找找其他 fib(n-1)、fib(n) 呢？想想确实很有意思哈哈。

还有一点就是 pow_mod 幂取模 也就是简单的 快速幂取余 的使用，也是 lrj 大佬在前面刚刚讲过的小知识点。

参见代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e3 + 50;
#define ULL unsigned long long

int f[MAXN][MAXN * 7], F[MAXN];

int pow_mod(ULL a, ULL b, int n) {
	if (b == 0) return 1;
	int x = pow_mod(a, b / 2, n);
	int res = (ULL)x * x % n;
	if (b % 2 == 1) res = res * a % n;
	return res;
}

int solve(ULL a, ULL b, int n) {
	if (a == 0 or n == 1) return 0;
	int x = pow_mod(a % F[n], b, F[n]);
	return f[n][x];
}

int main() {
	// memset(f, 0, sizeof(f));
	// memset(F, 0, sizeof(F));
	for (int n = 2; n <= 1000; ++n) {
		f[n][0] = 0, f[n][1] = 1;
		for (int i = 2; ; ++i) {
			f[n][i] = (f[n][i - 1] + f[n][i - 2]) % n;
			if (f[n][i - 1] == 0 and f[n][i] == 1) {
				F[n] = i - 1;
				break;
			}
		}
	}

	int t;
	scanf("%d", &t);
	ULL a, b;
	int n, res;

	while (t--) {
	    cin >> a >> b >> n;
	    cout << solve(a, b, n) << "\n";
	}
	/*
	// 一开始采用c语言形式输出未包含using namespace std;本地能过但是过不去oj，不知什么情况...
	// 靠，找到原因了，这个I64u在OJ上不支持，貌似只能支持llu，无语了...
	while (t--) {
		scanf("%llu%I64u%d", &a, &b, &n);
		res = solve(a, b, n);
		printf("%d\n", res);
	}
	*/
	return 0;
}