hdu-4565(矩阵快速幂+推导)

淡淡的烟草味﹌ 2022-06-09 05:39 188阅读 0赞

问题描述:

A sequence S n is defined as:Sn=\[(a+sqrt(b))^(n)\] % m,其中\[ \] 表示向下取整.

Input

There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 2 15, (a-1) 2< b < a 2, 0 < b, n < 2 31.The input will finish with the end of file

Output

For each the case, output an integer S n.

Sample Input

2 3 1 2013
    2 3 2 2013
    2 2 1 2013

Sample Output

4
    14
    4

题目题意;题目给我们a,b,n,m让我们求Sn %m.

题目分析:这道题目与hdu\_2256很像，这是是那道题目的链接[点击打开链接][Link 1]

这道题目，我也按照以前的方法再推导一遍;

![Center][]

答案就推导出来了。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #define ll long long
    using namespace std;
    
    ll a,b,n,mod;
    struct matrix
    {
        ll f[3][3];
        matrix operator * (const matrix &a) const {
            matrix res;
            for (int i=1;i<=2;i++) {
                for (int j=1;j<=2;j++) {
                    res.f[i][j]=0;
                    for (int k=1;k<=2;k++)
                        res.f[i][j]=(res.f[i][j]+(*this).f[i][k]*a.f[k][j])%mod;
                }
            }
            return res;
        }
    }A,B;
    
    matrix fast_pow(matrix base,int k)
    {
        matrix ans=base;
        while (k) {
            if (k&1)
                ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }
    
    void init()
    {
        B.f[1][1]=a,B.f[1][2]=b;
        B.f[2][1]=1,B.f[2][2]=a;
        A.f[1][1]=a,A.f[2][1]=1;
    }
    
    int main()
    {
        while (scanf("%lld%lld%lld%lld",&a,&b,&n,&mod)!=EOF) {
            if (n==1) { printf("%lld\n",(a+(ll) sqrt(b)+1)%mod);continue;}
            n-=2;
            init();
            struct matrix cur,ans;
            cur=B;
            cur=fast_pow(cur,n);
            ans=cur*A;
            printf("%lld\n",(2*ans.f[1][1])%mod);
    
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/wust_cyl/article/details/77644389
[Center]: /images/20220609/f217d692992b432c8069197889d22ac5.png