2016弱校联盟十一专场10.5 F. Fibonacci of Fibonacci

心已赠人 2022-07-16 04:51 124阅读 0赞

2016弱校联盟十一专场10.5 F. Fibonacci of Fibonacci 题目链接：[https://acm.bnu.edu.cn/v3/problem\_show.php?pid=52322][https_acm.bnu.edu.cn_v3_problem_show.php_pid_52322]

题面描述：

![Image 1][]

题面描述：

Find FFn mod 20160519.

题目分析：

由于斐波那契数对M求模运算一定会产生循环节，而这个第一层循环节很容易找到，在找到循环节之后，利用矩阵连乘，快速幂求解。

或者把两层的循环节都找到，直接打印好表求解。

代码实现：

方法一：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const long long M=20160519;
    const long long M1=26880696;
    const long long N=2;
    
    const int maxn=30000000;
    long long f[maxn];
    void qiuxunhuanjie(long long mod)
    {
        f[0]=0;
        f[1]=1;
        for(int i=2;i<maxn;i++)
        {
            f[i]=(f[i-1]%mod+f[i-2]%mod)%mod;
        }
        for(int i=mod-100;i<maxn;i++)
        {
            if(f[i]==1 && f[i+1]==1 && f[i+2]==2)
            {
                cout<<i<<endl;
                break;
            }
        }///i=26880697;
    }
    
    
    struct mat
    {
        long long m[N][N];
    };
    
    mat A=
    {
        1,1,
        1,0
    };
    
    mat I=
    {
        1,0,
        0,1
    };
    
    mat multi(mat a,mat b,long long mod)
    {
        mat c;
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                c.m[i][j]=0;
                for(int k=0; k<N; k++)
                    c.m[i][j]+=((a.m[i][k]%mod)*(b.m[k][j]%mod))%mod;
                c.m[i][j]%=mod;
            }
        }
        return c;
    }
    
    mat power(mat A,long long k,long long mod)//矩阵快速幂
    {
        mat ans=I,p=A;
        while(k)
        {
            if(k&1)///若k为奇数,
            {
                ans=multi(ans,p,mod);
                k--;
            }
            k>>=1;///k=k/2;
            p=multi(p,p,mod);
        }
        return ans;
    }
    
    int main()
    {
        ///qiuxunhuanjie(M);
        int T;
        long long n;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%lld",&n);
            mat ans=power(A,n-1,M1);
            int tmp=ans.m[0][0];
            //cout<<"tmp= "<<tmp<<endl;
            mat ans2;
            ans2=power(A,tmp-1,M);
            printf("%lld\n",ans2.m[0][0]);
        }
        return 0;
    }

方法二：

利用求解循环节的方法，将循环节求解出来，然后直接应用：

求循环节代码：

#include <iostream>
    #include <string.h>
    #include <algorithm>
    #include <stdio.h>
    #include <math.h>
    #include <map>
    
    using namespace std;
    
    typedef long long LL;
    
    const int M = 2;
    
    struct Matrix
    {
        LL m[M][M];
    };
    
    Matrix A;
    Matrix I = {1,0,0,1};
    
    Matrix multi(Matrix a,Matrix b,LL MOD)
    {
        Matrix c;
        for(int i=0; i<M; i++)
        {
            for(int j=0; j<M; j++)
            {
                c.m[i][j] = 0;
                for(int k=0; k<M; k++)
                    c.m[i][j] += a.m[i][k] * b.m[k][j];
                c.m[i][j] %= MOD;
            }
        }
        return c;
    }
    
    Matrix power(Matrix a,LL k,LL MOD)
    {
        Matrix ans = I,p = a;
        while(k)
        {
            if(k & 1)
            {
                ans = multi(ans,p,MOD);
                k--;
            }
            k >>= 1;
            p = multi(p,p,MOD);
        }
        return ans;
    }
    
    int gcd(int a,int b)
    {
        return b? gcd(b,a%b):a;
    }
    
    const int N = 400005;
    const int NN = 5005;
    
    int num[NN],pri[NN];
    int fac[NN];
    bool flag[NN];
    int c;
    
    bool prime[N];
    int p[N];
    int k;
    
    int cnt1;
    int pri1[NN],num1[NN];
    
    void isprime()
    {
        k = 0;
        memset(prime,true,sizeof(prime));
        for(int i=2; i<N; i++)
        {
            if(prime[i])
            {
                p[k++] = i;
                for(int j=i+i; j<N; j+=i)
                    prime[j] = false;
            }
        }
    }
    
    LL quick_mod(LL a,LL b,LL m)
    {
        LL ans = 1;
        a %= m;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a % m;
                b--;
            }
            b >>= 1;
            a = a * a % m;
        }
        return ans;
    }
    
    int legendre(int a,int p)
    {
        if(quick_mod(a,(p-1)>>1,p)==1) return 1;
        else                           return -1;
    }
    
    void Solve(int n,int pri[],int num[],int &cnt)
    {
        cnt = 0;
        int t = (int)sqrt(1.0*n);
        for(int i=0; p[i]<=t; i++)
        {
            if(n%p[i]==0)
            {
                int a = 0;
                pri[cnt] = p[i];
                while(n%p[i]==0)
                {
                    a++;
                    n /= p[i];
                }
                num[cnt] = a;
                cnt++;
            }
        }
        if(n > 1)
        {
            pri[cnt] = n;
            num[cnt] = 1;
            cnt++;
        }
    }
    
    void dfs(int dept,int cnt,LL product,int pri1[],int num1[])
    {
        if(dept == cnt)
        {
            fac[c++] = product;
            return;
        }
        for(int i=0; i<=num1[dept]; i++)
        {
            dfs(dept+1,cnt,product,pri1,num1);
            product *= pri1[dept];
        }
    }
    
    map<int,int> mp;
    
    LL find_loop(LL n)
    {
        int cnt = 0;
        Solve(n,pri,num,cnt);
        LL ans = 1;
        for(int i=0; i<cnt; i++)
        {
            int record=1;
            if(mp.find(pri[i]) != mp.end())
            {
                record = mp[pri[i]];
                goto Test;
            }
            if(pri[i]==2)
                record=3;
            else if(pri[i]==3)
                record=8;
            else if(pri[i]==5)
                record=20;
            else
            {
                if(legendre(5,pri[i])==1)
                {
                    c = 0;
                    Solve(pri[i]-1,pri1,num1,cnt1);
                    dfs(0,cnt1,1,pri1,num1);
                }
                else
                {
                    c = 0;
                    Solve(2*(pri[i]+1),pri1,num1,cnt1);
                    dfs(0,cnt1,1,pri1,num1);
                }
                sort(fac,fac+c);
                for(int r=0; r<c; r++)
                    flag[r] = 1;
                for(int k=c-1; k >= 0; k--)
                {
                    if(!flag[k]) continue;
                    Matrix a = power(A,fac[k]-1,pri[i]);
                    int x = (a.m[0][0]%pri[i]+a.m[0][1]%pri[i])%pri[i];
                    int y = (a.m[1][0]%pri[i]+a.m[1][1]%pri[i])%pri[i];
                    if(x==1 && y==0)
                    {
                        record = fac[k];
                    }
                    else
                    {
                        for(int j=0; j<=k; j++)
                        {
                            if(fac[k] % fac[j] == 0)
                                flag[j] = 0;
                        }
                    }
                }
                mp[pri[i]] = record;
            }
    Test:
            for(int k=1; k<num[i]; k++)
                record *= pri[i];
            ans=ans/gcd(ans,record)*record;
        }
        return ans;
    }
    
    void Init()
    {
        A.m[0][0] = 1;
        A.m[0][1] = 1;
        A.m[1][0] = 1;
        A.m[1][1] = 0;
    }
    
    int main()///求解循环节的函数，可以求得当斐波那契数对mod=20160519取模时，循环节为：26880696 ;当对mod=26880696取模时，循环节为：746688
    {
        //freopen("/Users/jamesqi/Desktop/in.txt","r",stdin);
        int T,n;
        Init();
        mp.clear();
        isprime();
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            LL ans = find_loop(n);
            printf("%lld\n",ans);
        }
        return 0;
    }

解题代码：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const long long M=20160519;
    const long long M1=26880696;
    const long long M2=746688;
    
    long long f[M1],f2[M2];
    void print()
    {
        f[0]=0;
        f[1]=1;
        f2[0]=0;
        f2[1]=1;
        for(int i=2;i<M1;i++)
        {
            f[i]=(f[i-1]%M+f[i-2]%M)%M;
        }
        for(int i=2;i<M2;i++)
        {
            f2[i]=(f2[i-1]%M1+f2[i-2]%M1)%M1;
        }
    }
    
    int main()
    {
        int T;
        long long n;
        scanf("%d",&T);
        print();
        while(T--)
        {
            scanf("%lld",&n);
            printf("%lld\n",f[f2[n%M2]]%M1);
        }
        return 0;
    }

[https_acm.bnu.edu.cn_v3_problem_show.php_pid_52322]: https://acm.bnu.edu.cn/v3/problem_show.php?pid=52322
[Image 1]: