qq网站在线登录网页版,中山市安全平台教育,tp5企业网站开发实例,专业建公司网站题意#xff1a;
给出64位整数a、b以及不超过1000的正整数n#xff0c;求斐波那契数列第a ^ b项模n的结果。 输入#xff1a;情况数T#xff0c;之后T行每行a、b、n。 输出#xff1a;斐波那契数列第a ^ b项模n的结果。
分析#xff1a;由于斐波那契数列的每一项都是由…题意
给出64位整数a、b以及不超过1000的正整数n求斐波那契数列第a ^ b项模n的结果。 输入情况数T之后T行每行a、b、n。 输出斐波那契数列第a ^ b项模n的结果。
分析由于斐波那契数列的每一项都是由前两项相加得来并且每一项都对n取模所有 每一项的情况一共有n种而相邻两项若组成有序数对则不同的数对的情况也只有 n ^ 2种所以只需要计算n * n项就可以找到数列规律。
题目
The i’th Fibonacci number f(i) is recursively defined in the following way:
• f(0) 0 and f(1) 1
• f(i 2) f(i 1) f(i) for every i ≥ 0
Your task is to compute some values of this sequence.
Input
Input begins with an integer t ≤ 10, 000, the number of test cases. Each test case consists of three integers a, b, n where 0 ≤ a, b 2 64 (a and b will not both be zero) and 1 ≤ n ≤ 1000.
Output
For each test case, output a single line containing the remainder of f(a b ) upon division by n.
Sample Input
3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000
Sample Output
1
21
250
AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
typedef unsigned long long ull;
int t;
ull m,n;
ull dp[1000010];/*范围*/
int k;
int dfs(ull a,ull b,int c)
{int ans1;int qa%c;while(b){if(b1)ansans*q%c;qq*q%c;b1;/*care 别忘了加是一个数学运算符号*/}return ans;
}
int main()
{scanf(%d,t);while(t--){scanf(%llu%llu%d,m,n,k);if(m0||k1){printf(0\n);continue;}dp[0]0;dp[1]1;int c;for(int i2; ik*k; i){dp[i](dp[i-1]dp[i-2])%k;if(dp[i]1dp[i-1]0)/*已经找出一个周期长度了在k*k内一定找得到*/{ci-1;break;}}int ansdfs(m,n,c);printf(%llu\n,dp[ans]);}return 0;
}
