链接：https://ac.nowcoder.com/acm/contest/903/B 来源：牛客网
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; int t; ll ppow(ll a, ll b,ll m) { ll ans = 1; while(b) { if(b&1) { ans = (ans * a) % m; b--; } b /= 2; a = a * a % m; } return ans ; } ll sum(ll a,ll b,ll m) { if(b==0) return 1; if(b%2) return (sum(a,b/2,m)*(1+ppow(a,b/2+1,m)))%m; else return ((sum(a,b/2-1,m))*(1+ppow(a,b/2+1,m))+ppow(a,b/2,m))%m; } int main() { scanf("%d",&t); while(t--) { ll n,p,q; scanf("%lld%lld%lld",&q,&n,&p); printf("%lld\n",(sum(q,n,p)-1)%p); } return 0; }
