51Nod--1013 3的幂的和
题目链接：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 ，我们需要用到快速幂：
用这种思路求 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
在这题中， 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;
}