UVA-11582-Colossal Fibonacci Numbers! (模算数,鸽巢原理)

2018年2月3日 0 条评论 7 次阅读 0 人点赞

题目链接:UVA - 11582

题目大意:f(x)代表斐波那契数列的第x项,求f(ab)%n  (0<=a,b<=264

题目分析:

取余我们可以想到鸽巢原理,%n,则f[i]的可能数值只有n种,则f[i],f[i+1]的组合只有n2种,只需要求出n*n项左右就会出现

循环,酱~

ps.注意用ull

pps.从前出过一个应用鸽巢原理的题目,可惜当时并不会,哎😔

给出代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=1000+100;
int f[maxn*maxn];
int mod;
int T;
void solve(int n)
{
    f[0]=0%mod;
    f[1]=1%mod;
    for(int i=2;i<=n+100;i++)
    {
        f[i]=(f[i-1]+f[i-2])%mod;
        if(f[i]==f[1]&&f[i-1]==f[0])
        {
            T=i-1;
            return;
        }
    }
}
int pow_mod(unsigned long long int x,unsigned long long int n,unsigned long long int MOD)
{
    unsigned long long int ans=1;
    x=x%MOD;
    while(n>0)
    {
        if(n%2)
            ans=(ans*x)%MOD;
        x=(x*x)%MOD;
        n=n/2;
    }
    return ans;
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        unsigned long long int a,b;
        cin>>a>>b>>mod;
        solve(mod*mod);
        //cout<<T<<endl;
        int k=pow_mod(a%T,b,T);
        //cout<<k<<endl;
       // cout<<k<<endl;
        cout<<f[k]<<endl;
    }
    return 0;
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)