題目鏈接：https://ac.nowcoder.com/acm/contest/903/B

---

?

題意： 給你 q,n,p,求 q¹+q²+...+q^n?的和 模 p。

思路：一開始不會(huì)做，后面查了下發(fā)現(xiàn)有個(gè)等比數(shù)列求和的快速冪公式，附上鏈接https://www.cnblogs.com/yuiffy/p/3809176.html

AC代碼：

1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 long long mod; 5 long long n,q; 6 long long Fastpow(long long a,long long b) 7 { 8 long long x = 1; 9 while(b > 0) 10 { 11 if(b % 2 != 0) 12 { 13 x = x * a % mod; 14 } 15 a = a * a % mod; 16 b /= 2; 17 } 18 return x; 19 } 20 long long T(long long n)//等比數(shù)列快速求和核心公式 21 { 22 if(n == 0) return 1; 23 if(n == 1) return q; 24 if(n % 2 == 0) 25 { 26 return (Fastpow(q,n/2)+1 )%mod * T(n/2)%mod; 27 } 28 else 29 { 30 return (Fastpow(q,n) + T(n-1))%mod; 31 } 32 } 33 int main() 34 { 35 int t; 36 scanf("%d",&t); 37 while(t--) 38 { 39 scanf("%lld%lld%lld",&q,&n,&mod); 40 q %= mod; 41 printf("%lld\n",T(n)); 42 } 43 return 0 ; 44 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Carered/p/10924788.html

總結(jié)

以上是生活随笔為你收集整理的2019河北省大学生程序设计竞赛（重现赛）B 题 -Icebound and Sequence （ 等比数列求和的快速幂取模）...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。