链接:https://ac.nowcoder.com/acm/contest/903/B
题意：
Icebound hates math. But Imp loves math. One day, Imp gave icebound a problem.
The problem is as follows.
S=(∑ni=1qi） mod pS=(∑i=1nqi） mod p
For given q,n,p, you need to help icebound to calculate the value of S.
思路：
等比数列求和。
因为考虑到取余，所以不能直接算。
令S(n) 为等比数列前n项和。
若n为偶数：
S(n) = S(n/2) + S(n/2)*a^(n/2) (因为第i(i <= n/2)项和i+n/2项存在第i项乘a^(n/2)等以第i+n/2项的值。
若n为奇数：
S(n) = S(n/2) + S(n/2)*a^(n/2) + a^n
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, q, p;
LL QM(LL a, LL b, LL m)
{
LL res = 1;
while (b)
{
if (b&1)
res = (res*a)%m;
a = (a*a)%m;
b >>= 1;
}
return res;
}
LL GetR(int t)
{
if (t == 1)
return n%p;
if (t%2 == 0)
return (GetR(t/2)+(GetR(t/2)*QM(n, t/2, p))%p)%p;
else
return ((GetR(t/2)+(GetR(t/2)*QM(n, t/2, p))%p)%p+QM(n, t, p))%p;
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n >> q >> p;
cout << GetR(q) << endl;
}
return 0;
}
原文链接: https://www.cnblogs.com/YDDDD/p/10923486.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/295575
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
