题目链接：https://ac.nowcoder.com/acm/contest/903/B 题目大意： 模板：等比数列二分求和(logn复杂度)https://www.cnblogs.com/s1124yy/p/6649400.html
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; int M; typedef long long LL; LL power(LL a,LL b) { LL ans = 1; a %= M; while(b) { if(b & 1) { ans = ans * a % M; b--; } b >>= 1; a = a * a % M; } return ans; } LL sum(LL a,LL n) { if(n == 1) return a; LL t = sum(a,n/2); if(n & 1) { LL cur = power(a,n/2+1); t = (t + t * cur % M) % M; t = (t + cur) % M; } else { LL cur = power(a,n/2); t = (t + t * cur % M) % M; } return t; } int main() { int t; scanf("%d",&t); LL n, q, p; while(t--) { scanf("%lld%lld%lld",&q,&n,&M); printf("%lld\n",sum(q,n)); } return 0; }