hdu-4549(矩阵快速幂+欧拉定理)

客官°小女子只卖身不卖艺 2022-06-09 04:59 129阅读 0赞

问题描述:

M斐波那契数列F\[n\]是一种整数数列，它的定义如下：   
  
F\[0\] = a   
F\[1\] = b   
F\[n\] = F\[n-1\] \* F\[n-2\] ( n > 1 )   
  
现在给出a, b, n，你能求出F\[n\]的值吗？

Input

输入包含多组测试数据；   
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）

Output

对每组测试数据请输出一个整数F\[n\]，由于F\[n\]可能很大，你只需输出F\[n\]对1000000007取模后的值即可，每组数据输出一行。

Sample Input

0 1 0
    6 10 2

Sample Output

0
    60

题目题意:题目给我们一个n让我们求出一个新的斐波拉契数列的f(n) % 1e9+7.

题目分析:这个题目虽然与原来的斐波拉契数列样子不一样，但是实质是一样的，对于a,b来说它们的指数符合斐波拉契数列的规则f(n)=f(n-1)+f(n-2),只是需要注意的是它们的f(0)与f(1)的值不一样，我们用矩阵快速幂快速的跑出a与b的指数，剩下的就是计算a^(x1) %c与b^(x2) %c

这个地方我TLE好多发，发现这个地方才是这道题目的难点。

我们对于A^B %C 来说

我最开始的想法就是:

对于A^x % mod 的式子，我们有如下的展开式：

A^x % mod=A^(x%phi\[mod\]+phi\[mod\])%mod (当且仅当x>=phi\[mod\]时成立) (在我之前的博客里面，我利用过该公式)

但是这个地方不行，因为mod 非常大，没有什么作用)

下面我们要利用欧拉定理来解决:在[数论][Link 1]中，欧拉定理,（也称[费马][Link 2]\-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为[正整数][Link 3]，且n,a[互质][Link 4]，则:![0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg][]

对于A^B %C 来说,我们令x\*phi\[C\]+y=B,则等于A^(x\*phi\[C\]+y) %C

A^(x\*phi\[C\]+y) %C=A^(x\*phi\[C\])%C  \*  A^(y) %C =(A^(phi\[C\]) %C)^x \*A^(y) %C  发现没有，前面的式子就是欧拉定理表达式等于1

则原始式子等于A^(y) %C  因为C为素数则phi\[C\]=C-1，则y=B%(phi\[C\])=B%(C-1);

即:A^B %C =A^(B%(C-1)) %C

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    const int mod=1e9+7;
    int a,b,n;
    
    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]);
                    res.f[i][j]=res.f[i][j]%(mod-1);
                }
            }
            return res;
        }
    }ppow;
    
    void init()//常数矩阵
    {
        ppow.f[1][1]=ppow.f[1][2]=1;
        ppow.f[2][1]=1;
    }
    
    matrix fast_pow1(matrix base,int k)//快速幂 矩阵
    {
        matrix ans=base;
        while (k) {
            if (k&1)
                ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }
    
    ll fast_pow2(ll base,ll k)//快速幂 数
    {
        ll ans=1;
        base=base%mod;
        while (k) {
            if (k&1)
                ans=ans*base%mod;
            base=base*base%mod;
            k>>=1;
        }
        return ans;
    }
    
    int main()
    {
        init();
        while (scanf("%d%d%d",&a,&b,&n)!=EOF) {
            if (n==0) { printf("%d\n",a%mod); continue;}
            if (n==1) { printf("%d\n",b%mod); continue;}
            n-=2;
            ll sum=1;
            struct matrix cur;
            cur=ppow;
            cur=fast_pow1(cur,n);
            sum=fast_pow2(a,cur.f[1][2])%mod;//a 和 b的指数保存的位置不一样 注意
            sum=sum*fast_pow2(b,cur.f[1][1])%mod;
            printf("%lld\n",sum);
        }
        return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E8%AE%BA
[Link 2]: https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC
[Link 3]: https://baike.baidu.com/item/%E6%AD%A3%E6%95%B4%E6%95%B0
[Link 4]: https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8
[0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D116/sign=b4a8aa2a7dd98d1072d40830173eb807/0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg