二分递归求等比数列前n项和

2019河北省大学生程序设计竞赛（重现赛）Ｂ
我们假设有一个等比数列: a[n] = q ^ n
那么 S[n] = q ^ 1 + q ^ 2 + q ^ 3 …… + q ^ n
正常情况我们有 S[n] = q * (1 - q ^ n) / (1 - q)
若我们需要求的是 S[n] % mod 且 (1 - q)与ｍod不互质，那么上面的公式便会有问题(逆元无法确定)
这时候我们发现：
如果n为奇数: S[n] = S[n / 2] + a[(n - 1) / 2 + 1]×S[n / 2] + a[(n - 1) / 2 + 1]
如果n为偶数: S[n] = S[n / 2] + a[n / 2]×S[n / 2]

证明

如果n为偶数，我们可以将n分成两个部分，S[n] = S[n / 2] + 后一部分
然后我们发现后一部分其实可以又前一部分乘一个数得来，这个数为a[n / 2 + 1] / a[1],即为q ^ (n / 2)
如果n为奇数，我们可以类比偶数情况，在两部分间加一个数，这样第一部分和第三部分同偶数情况处理，在额外加上中间的数

代码

/*
二分求等比数列前ｎ项和(首项等于公比)
(1)当n为偶数,可将ｎ分为前后两个部分,后部分可以看成前部分每项乘以q^k,这个k即为n/2
(2)当n为奇数，同理偶数，可看成三个部分，前后部分与偶数类似，中间部分是一个数，即为a[(n - 1) / 2 + 1],前后部分之间需乘以q^((n - 1) / 2 + 1) 
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n, q, p;
ll q_pow(ll a, ll b)
{
    ll c = 1;
    while(b)
    {
        if(b & 1)
            c = (c * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return c;
}
ll dfs(ll x)
{
    if(x == 1)
        return q;
    ll dd = dfs(x / 2);
    if(x & 1)//(1 + a[n / 2 + 1]) * S[n / 2] + a[n / 2 + 1]
    {
        ll zz = q_pow(q, x / 2 + 1);
        dd = (dd + dd * zz % p) % p;
        dd = (dd + zz) % p;
    }
    else //(1 + a[n / 2]) * S[n / 2]
    {
        ll zz = q_pow(q, x / 2);
        dd = (dd + dd * zz % p) % p;
    }
    return dd;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t --)
    {
        cin >> q >> n >> p;
        cout << dfs(n) << endl;
    }
}