首页 > 代码库 > 11582 - Colossal Fibonacci Numbers!

11582 - Colossal Fibonacci Numbers!

  • f (0) = 0 and f (1) = 1
  • f (i+2) = f (i+1) + f (i)  for every i ≥ 0

Sample input

three integers a,b,n where 0 ≤ a,b < 264 (a and b will not both be zero) and 1 ≤ n ≤ 1000.

T

a  b  n 
3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

Sample output

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

1
21
250
从数据上来看,2^64,需要用到unsigned long long (2^64-1)
从题目类型上来看,你就是用java也算不完这么大的数,所以果断是个循环规律题目
从方法上来看,既然有规律,则有找规律的方法。由fibonacci数列的性质来看,每个数字都是有前两个数字所决定的,且最前面两个数字分别为f【0】=0和f【1】=1,所以一旦出现相邻的两个数字满足相邻的0和1,则循环出现。
从代码方面来看,给高次幂取模可以用分治法,时间复杂度为O(logn),技巧性也不高,易于掌握易于接受。
从细节方面来看,不要盲目把数据开大,需要用到大数据类型的用,不需要的就不要用,理清思路才能明确需要,保证代码的清晰可读性。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;


int pow_mod(int a,ull b,int p)
{
    if(b==0) return 1;
    int x = pow_mod(a,b/2,p);
    ull ans = (ull)x * x % p;
    if(b%2==1) ans= ans * a % p;
    return (int)ans;
}
const int maxn = 1005;
int f[maxn*maxn];
int main()
{
    int t;
    scanf("%d",&t);
    ull a,b;int n;
    while(t--)
    {
        scanf("%I64u%I64u%d",&a,&b,&n);
        if(a==0||n==1)
        {
            printf("0\n");
        }
        else
        {
            int period;
            f[0]=0;f[1]=1;
            for(int i=2;;i++)
            {
                int temp = (f[i-1]+f[i-2])%n;
                f[i]=temp;
                if(f[i]==1&&f[i-1]==0)
                {
                    period = i-1;
                    break;
                }
            }
            int c = pow_mod(a%period,b,period);
            printf("%d\n",f[c]);
        }
    }
    return 0;
}

算是第一道数学题吧,做数学,就该多想想多理理多总结总结。明白清楚为止~