2019河北省大學生程序設計競賽（重現賽）B 題 -Icebound and Sequence （等比數列求和的快速冪取模）...

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

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

思路：一開始不會做，后面查了下發現有個等比數列求和的快速冪公式，附上鏈接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)//等比數列快速求和核心公式
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 }

轉載于:https://www.cnblogs.com/Carered/p/10924788.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/248880.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/248880.shtml
英文地址，請注明出處：http://en.pswp.cn/news/248880.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！