wyh的数列~（坑爹题目）

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

题目描述

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

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

输入描述:

输入第一行一个整数T(1<=T<=100)，代表测试组数
接下来T行，每行三个数 a,b,c (a,b<=2^64) (1<c<1000)

输出描述:

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

输入例子:

3

1 1 2

2 3 1000

32122142412412142 124124124412124 123

输出例子:

-->

示例1

输入

3

1 1 2

2 3 1000

32122142412412142 124124124412124 123

输出

1

21

3

这题超级超级坑爹 ，专门卡着long long ，要用unsigned long long ，
由于这个原因我卡了好久好久。
这个题目不断的取模，会使得斐波那契数列形成一个环.
然后就是一个快速幂取模。

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define llu unsigned long long

 const int maxn=1e5+;

 llu f[maxn];

 llu modexp(llu a,llu b,llu c)

 {

     llu res=,temp=a%c;

     while(b){

         if (b&) res=res*temp%c;

         temp=temp*temp%c;

         b=b>>;

     }

     return res;

 }

 int main(){

     int t;

     scanf("%d",&t);

     while(t--){

         llu a,b,c;

         scanf("%llu%llu%llu",&a,&b,&c);

         f[]=,f[]=;

         for (int i= ; ;i++){

             f[i]=(f[i-]+f[i-])%c;

             if (f[i]== && f[i-]==) {

                 c=i-;

                 break;

             }

         }

         printf("%llu\n",f[modexp(a,b,c)]);

     }

     return ;

 }

巴特西

wyh的数列~（坑爹题目）

题目描述

输入描述:

输出描述:

输入例子:

输出例子:

输入

输出

最新文章

热门文章