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;
}
}
