Problem F: Colossal Fibonacci Numbers!

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 begins with an integer?t?≤?10,000,the number of test cases. Each test case consists of three integers?a,b,nwhere 0?≤?a,b?<?264?(a?and?b?will not both be zero) and 1?≤?n?≤?1000.

For each test case,output a single line containing the remainder of?f?(ab)?upon division by?n.

Sample input

3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

Sample output

1
21
250

一.大数取模，幂取模，模的计算方法

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
const int maxn=1000+10;
ull F[maxn*maxn];
int power(ull a,ull b,int t) {
    ull result = 1;
    while(b) {
        if(b%2) {
            result = (a*result)%t;
        }
        a = (a*a)%t;
        b/=2;
    }
    return result;
}

int main()
{
    freopen("/Users/zhangjiatao/Documents/暑期训练/input.txt","r",stdin);
    int T;
    cin>>T;
    while(T--)
    {
        ull a,n,l;
        int flag=1;
        cin>>a>>b>>n;
        F[0]=0;
        F[1]=1;
        for(ull i=2;i<=n*n;i++)
        {
            F[i]=(F[i-1]%n+F[i-2]%n)%n;
            if(F[i]==F[1]&&F[i-1]==F[0])
            {
                l=i-1;
                break;
            }
        }
         if(a == 0 || n == 1) printf("0n");
        else cout<<F[power(a%l,l)]<<endl;
    }
    return 0;
}

（编辑：邯郸站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!