51Nod--1013 3的幂的和

布满荆棘的人生 2022-06-14 07:47 136阅读 0赞

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1013][http_www.51nod.com_onlineJudge_questionCode.html_problemId_1013]

基准时间限制：1 秒 空间限制：131072 KB

求：3^0 + 3^1 +…+ 3^(N) mod 1000000007  
Input  
输入一个数N(0 <= N <= 10^9)  
Output  
输出：计算结果  
Input示例  
3  
Output示例

题目给的数据很明显是一个首项为 1，公比为 3 的等比数列，按照要求，我们只需要求出这个等比数列的前 n 项和然后取模 1000000007 就可以了，当 n 过大的时候为了防止数据溢出我们需要用到一个规律：  
a^n % mod = (((((a%mod)\*a)%mod)\*a%mod)\*a%mod)…  
等比数列前 n 项和：a1(1-q^n)/(1-q) 。为了快速求 q^n ，我们需要用到快速幂：

![这里写图片描述][SouthEast]

用这种思路求 q^n 的时间复杂度为O(logn)，下面是对应代码：

// mod 为 1000000007 
    ll getPow(ll x, ll n) {
        ll res = 1;
        while(n>0) {
            // 如果是奇数
            if(n&1) {
                res = res*x%mod;
            }
            x = x*x%mod;
            // 右移一位，指数除以2
            n >>= 1;
        }
        return res; 
    }

这样求出的结果因为对 mod 取余了，不一定能被 (1-q) 整除(等比数列前 n 项和 s(n) = a1\*(1-q^n)/(1-q))，所以要想办法把除法变成乘法，或者换一种求和方法。如果采用第一种方法，需要用到逆元的思想：

若对于数字 A, C 如果存在 X，使得 A * X = 1 (mod C) 成立, 那么称 X 为 A 对C的乘法逆元。

例如：4关于1模7的乘法逆元为多少？  
4X≡1 mod 7  
这个方程等价于求一个X和K，满足  
4X=7K+1  
其中X和K都是整数。  
若ax≡1 mod f, 则称a关于模f的乘法逆元为x。也可表示为ax≡1(mod f)。  
当a与f互素时，a关于模f的乘法逆元有解。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。  
例如，求5关于模14的乘法逆元：  
14=5\*2+4  
5=4\*1+1  
说明5与14互素，存在5关于14的乘法逆元。  
1=5-4=5-(14-5\*2)=5\*3-14  
因此，5关于模14的乘法逆元为3。

以上例子来源于百度百科：[http://baike.baidu.com/item/%E4%B9%98%E6%B3%95%E9%80%86%E5%85%83][http_baike.baidu.com_item_E4_B9_98_E6_B3_95_E9_80_86_E5_85_83]

在这题中， 2 关于 1000000007 的乘法逆元为 500000004 （2\*500000004 = 1000000007 … 1）

那么代码就可以写出来了：

#include <iostream>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const ll mod = 1000000007;
    
    ll getPow(ll x, ll n) {
        ll res = 1;
        while(n>0) {
            if(n&1) {
                res = res*x%mod;
            }
            x = x*x%mod;
            n >>= 1;
        }
        return res; 
    }
    
    int main() {
        ll n;
        ll res;
        while(cin >> n) {
            res = getPow(3, n+1);
            cout << (res-1)*500000004%mod << endl;
        }
    
        return 0;
    }

下一种方法是换一种求和的方法，即不采用等比数列的前 n 项和公式，这里我们可以用下面的代码求和：

// 求首项为 a, 公比为 a 的等比数列的前 n 项和 
    ll sum(ll a, ll n) {
        if(n == 1) {
            return a;
        }
        // 先求出前面半数据的和 
        ll c = sum(a, n>>1)%mod;
        // 利用前面一半的数据求出后面一半的数据的和 
        c = (c + c*getPow(a, n>>1)%mod)%mod;
        if(n&1) {
            // 如果 n 是奇数，还得加上最后一项 
            c = c + getPow(a, n)%mod;
        }
        return c%mod;
    }

这种方法的时间复杂度为O(logn)。对于题中的数据已经够小了

最后是第二种方法的代码：

#include <iostream>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const ll mod = 1000000007;
    
    ll getPow(ll x, ll n) {
        ll res = 1;
        while(n>0) {
            if(n&1) {
                res = res*x%mod;
            }
            x = x*x%mod;
            n >>= 1;
        }
        return res; 
    }
    
    // 求首项为 a, 公比为 a 的等比数列的前 n 项和 
    ll sum(ll a, ll n) {
        if(n == 1) {
            return a;
        }
        // 先求出前面半数据的和 
        ll c = sum(a, n>>1)%mod;
        // 利用前面一半的数据求出后面一半的数据的和 
        c = (c + c*getPow(a, n>>1)%mod)%mod;
        if(n&1) {
            // 如果 n 是奇数，还得加上最后一项 
            c = c + getPow(a, n)%mod;
        }
        return c%mod;
    }
    
    int main() {
        ll n;
        ll res;
        while(cin >> n) {
            res = sum(3, n);
            // 加上第一项的 1(3^0)  
            cout << (res+1)%mod << endl;
        }
    
        return 0;
    }

[http_www.51nod.com_onlineJudge_questionCode.html_problemId_1013]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1013
[SouthEast]: /images/20220614/ef2a17c5829e4738947154a876f9e8ae.png
[http_baike.baidu.com_item_E4_B9_98_E6_B3_95_E9_80_86_E5_85_83]: http://baike.baidu.com/item/%E4%B9%98%E6%B3%95%E9%80%86%E5%85%83