UVA 11582 巨大数的斐波那契数列 (大数取模，幂取模，模的计算方

发布时间：2021-02-20 15:16 所属栏目：125 来源：网络整理

导读：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 seq

Problem F: Colossal Fibonacci Numbers!

Oooh...pretty

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

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

1. (a+b)%n=(a%n+b%n)%n 2.(a-b)%n=(a%n-b%n+n)%n 3.(a*b)%n=(a%n*b%n)%n

一.问题分析及解决
想啊，这个问题明明以前都做过很类似的问题的，F[i]%n，那么应该很自然的去想F[i]%n=(F[i-1]%n+F[i-2]%n)%n,接下来应该就会发现要求的东西只要知道前两个数的模就好了，那就很自然的转化到以前的找规律问题上来

#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("0\n");
        else cout<<F[power(a%l,l)]<<endl;
    }
    return 0;
}

（编辑：ASP站长网）