K-wyh的数列

布满荆棘的人生 2022-05-27 04:28 114阅读 0赞

链接：https://www.nowcoder.com/acm/contest/93/K  
来源：牛客网

Problem Description：

wyh学长特别喜欢斐波那契数列，F（0）=0，F（1）=1，F（n)=F(n-1)+F(n-2)(n>=2)

一天他突发奇想，想求F（a^b）%c

Input：

输入第一行一个整数T(1<=T<=100)，代表测试组数

接下来T行，每行三个数 a,b,c (a,b<=2^64) (1<c<1000)

Output：

输出第a^b项斐波那契数对c取余的结果

Sample Input：

3  
1 1 2  
2 3 1000

32122142412412142 124124124412124 123

Sample Output：

1  
21

3

思路：n很小，斐波那契有循环节，求出循环节然后快速幂即可，2^64要注意用unsigned long long。

My DaiMa：

\#include<stdio.h>  
\#include<iostream>  
using namespace std;  
typedef unsigned long long ull;  
const int maxn=1010;  
ull F\[maxn\*maxn\];  
int powerMod(ull a,ull b,ull mod)  
\{  
int result=1;  
while(b)  
\{  
if(b&1)  
result=(a\*result)%mod;  
a=(a\*a)%mod;  
b/=2;  
\}  
return result;  
\}  
int main()  
\{  
ull a,b,c,mod,t;  
cin>>t;  
while(t--)  
\{  
cin>>a>>b>>c;  
F\[0\]=0;  
F\[1\]=1;  
for(int i=2;i<=c\*c;i++)  
\{  
F\[i\]=((F\[i-1\]%c)+F\[i-2\]%c)%c;  
if(F\[i\]==F\[1\]&&F\[i-1\]==F\[0\])  
\{  
mod=i-1;  
break;  
\}  
\}  
if(a==0||c==1)  
printf("0\\n");  
else  
cout<<F\[powerMod(a%mod,b,mod)\]<<endl;  
\}  
return 0;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读

相关 Fibonacci数列

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

淡淡的烟草味﹌/ 2022年11月11日 14:50/ 0 赞/ 207 阅读

相关 python翻转数列_翻转数列

第一次做这样的题，过程曲折，光获取m、n就试了各种方式，一开始没用脑子，直接写了个循环，虽然感觉一亿次循环肯定是不对的，但是还是一根筋的先写了，想看看能够case百分之多少，后

绝地灬酷狼/ 2022年11月01日 00:51/ 0 赞/ 201 阅读

相关 Farey数列 (法雷数列)

以下整理自：http://www.cnblogs.com/genyuan/archive/2012/08/29/2662598.html 及http://blog.csdn.

Dear 丶/ 2022年09月17日 11:24/ 0 赞/ 184 阅读

相关 fibonacci数列

斐波那契递归：1,1,2,3,5,8,13,21,34,......，用递归表示： fibonacci(1)=fibonacci(2)=1， fibonacci(n)=fi

左手的ㄟ右手/ 2022年08月04日 12:42/ 0 赞/ 199 阅读

相关 Fibonacci数列

<table style=""> <tbody style="margin-top:0px; margin-right:0px; margin-bottom:0px; ma

朴灿烈づ我的快乐病毒、/ 2022年06月10日 12:57/ 0 赞/ 220 阅读

相关数列有序

题目：一个非递减有序的整型数组有n个元素，给定一个整数num，将num插入该序列的适当位置，使序列仍保持非递减有序。要求定义一个函数insert()，将整数num插入在数组

秒速五厘米/ 2022年06月02日 05:19/ 0 赞/ 213 阅读

相关 K-wyh的数列

链接：https://www.nowcoder.com/acm/contest/93/K 来源：牛客网 Problem Description： wyh学长特别喜

布满荆棘的人生/ 2022年05月27日 04:28/ 0 赞/ 115 阅读

相关数列求和

问题 - 答：数列求和时间限制：1秒内存限制：4 MB 提交：324解决：207 \[ [提交][Link 1] \] \[ [状态][Link 2] \] \

快来打我*/ 2022年05月22日 12:20/ 0 赞/ 191 阅读

相关 Fibonacci数列

package ll; public class F { public static int factorial(int n){

叁歲伎倆/ 2021年09月27日 11:44/ 0 赞/ 404 阅读

相关数列排序

蓝桥杯学习记录 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

系统管理员/ 2021年07月24日 12:48/ 0 赞/ 341 阅读