给定一个a,n, 求$\sum_{i=0}^{n}{a_i}$

输入格式:

第一行输入两个整数a(1≤a≤109)与n(0≤n≤1018).

输出格式:

输出$\sum_{i=0}^{n}{a_i}$的值, 答案可能很大， 请你将答案与10^9^+7取模

输入样例1:

1
3 2

输出样例1:

1
13

样例解释：3^0^+3^1^+3^2^=13

输入样例2:

1
1000000 1000000000000000000

输出样例2:

1
143480269

思路

可使用等比数列求和公式，即快速幂+逆元运算

也可快速幂+二分，本题解使用此方法。

计算等比数列前n项和，有如下规则：
$$
当n是偶数时：s(n)=s(\frac{n}{2})+s(\frac{n}{2})a^{\frac{n}{2}} \
当n是奇数时：s(n)=s(\frac{n}{2})+s(\frac{n}{2})a^{\frac{n}{2}}+a^{n}
$$
注意题目是(n+1)项

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>

using namespace std;
using ll = long long;
const long long MOD = 1e9 + 7;

ll quick(ll a, ll b) {
    if(b == 0) {
        return 1;
    }
    long long t = quick(a, b / 2);
    return b % 2 == 0 ? t % MOD * t % MOD % MOD : t % MOD * t % MOD * a % MOD % MOD;
}

ll sum(ll a, ll b) { //计算a^1+a^2+a^3+...+a^b，一共b项
    if(b == 0 || a == 0)
        return 0;
    if(b == 1) //二分出口
        return a;
    if(b % 2 == 0)
        return ((1 + quick(a, b / 2)) * sum(a, b / 2)) % MOD;
    else
        return ((1 + quick(a, b / 2)) * sum(a, b / 2) + quick(a, b)) % MOD;
}

int main() {
    ll a, n;
    cin >> a >> n;
    //sum(a,n)计算n项，题目要求计算(n+1)项，需加a^0
    cout << sum(a, n) + 1 << endl;
    return 0;
}