51Nod 1013 3的幂的和（快速幂取模+逆元）

深碍√TFBOYSˉ_ 2022-09-25 08:28 156阅读 0赞

51Nod 1013 3的幂的和 （快速幂取模+逆元）：[http://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1013][http_www.51nod.com_onlineJudge_questionCode.html_problemId_1013]

题面描述：

[1013 3的幂的和][http_www.51nod.com_onlineJudge_questionCode.html_problemId_1013] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 20 [难度：3级算法题][3]

![star.png][] 收藏

![plus.png][] 关注

求：3^0 + 3^1 +...+ 3^(N) mod 1000000007

Input

输入一个数N(0 <= N <= 10^9)

Output

输出：计算结果

Input示例

Output示例

题目大意和分析：

根据等比数列求和公式，所求原式为：(3^(n+1)-1)/2(mod)M

根据运算规则，先计算一步2的逆元，然后利用快速幂求解指数部分，即可求得结果。

代码实现一：（利用扩展欧几里得求解逆元）

#include <iostream>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    const long long mod=1000000007;
    
    long long inv(long long a)
    {
        if(a==1)
            return 1;
        return inv(mod%a)*(mod-mod/a)%mod;
    }
    
    long long quick_mod(long long a,long long b)
    {
        long long ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%mod;
                b--;
            }
            b/=2;
            a=a*a%mod;
        }
        return ans;
    }
    
    int main()
    {
        long long n;
        while(scanf("%lld",&n)!=EOF)
        {
            long long ans=0;
            ans=quick_mod(3,n+1);
           // printf("%lld\n",ans);
            ans=(ans-1)*inv(2);
            ans=ans%mod;
            printf("%lld\n",ans);
        }
        return 0;
    }

代码实现二：（笔算求解逆元）

#include <iostream>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    const long long mod=1000000007;
    
    //long long inv(long long a)
    //{
    //    if(a==1)
    //        return 1;
    //    return inv(mod%a)*(mod-mod/a)%mod;
    //}
    
    long long quick_mod(long long a,long long b)
    {
        long long ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%mod;
                b--;
            }
            b/=2;
            a=a*a%mod;
        }
        return ans;
    }
    
    int main()
    {
        long long n;
        while(scanf("%lld",&n)!=EOF)
        {
            long long ans=0;
            ans=quick_mod(3,n+1);
           // printf("%lld\n",ans);
            //ans=(ans-1)*inv(2);
            //cout<<inv(2)<<endl;
            ans=(ans-1)*(500000004);
            ans=ans%mod;
            printf("%lld\n",ans);
        }
        return 0;
    }

[http_www.51nod.com_onlineJudge_questionCode.html_problemId_1013]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1013
[ok.png]: http://file.51nod.com/images/icon/ok.png
[3]: http://www.51nod.com/onlineJudge/problemList.html#!groupId=4
[star.png]: http://file.51nod.com/images/icon/star.png
[plus.png]: http://file.51nod.com/images/icon/plus.png