Fork me on GitHub

UVa-11582-Fibonacci数列f(a^b)%n的值

发表于 | 分类于
字数统计: 392字 | 阅读时长 ≈ 2分钟

题面

传送门:UVa-11582
题目大意:给出long long范围的a,b,n,求出f(a^b) % n的值,其中f(x)为Fibonacci数列的第x项.

样例

Sample Input
3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000
Sample Output
1
21
250

思路

一开始的思路是利用Fibonacci的通项公式加上二项式定理来求出a^b%n的项
但是无奈推公式时推错而且发现a^b%n的值和f(a^b)%n毫无关系.
联想到fibonacci数列对一个数n取mod,可以由鸽巢原理证明,

于是就诞生了做法.
先找出最小循环节，在这个循环节中寻找f(a^b)的位置.

代码

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000 + 5;
typedef unsigned long long ULL;

int f[maxn][maxn*6], period[maxn];

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

int solve(ULL a, ULL b, int n) 
{
	if(a == 0 || n == 1) return 0; 
	int p = pow_mod(a % period[n], b, period[n]);
	return f[n][p];
}

int main(int argc,char *argv[]) 
{
	ios::sync_with_stdio(false);//取消cin与scanf同步加快速度.
	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 && f[n][i] == 1)
			{
				period[n] = i - 1;
				break;
			}
		}
	}
	ULL a, b;
	int n, T;
	cin >> T;
	while(T--) 
	{
		cin >> a >> b >> n;
		cout << solve(a, b, n) << "\n";
	}
	return 0;
}