2019河北省赛 Icebound and Sequence（二分）

链接：https://ac.nowcoder.com/acm/contest/903/B 来源：牛客网

Icebound and Sequence

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 65536K，其他语言131072K 64bit IO Format: %lld

题目描述

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.

输入描述:

The first line contains an integer T, denoting the number of test cases. The next T lines, each line contains three integers q,n,p, separated by spaces. 1≤T≤1001≤T≤100, 1≤n,q,p≤1091≤n,q,p≤109

输出描述:

For each test case, you need to output a single line with the integer S.

示例1

输入

复制

2 2 3 100 511 4 520

输出

复制

14 184

---

二分求等比数列的和 

#include<bits/stdc++.h> #define lom long long using namespace std; lom quick(lom a,lom b,lom c)//quick mod { lom ans=1; a%=c; while(b) { if(b&1) ans=ans*a%c; a=a*a%c; b>>=1; } return ans%c; } lom sum(lom a,lom b,lom p) {// get the sum of the sequence of equal ratio numbers by bisection if(b==0) return 1; if(a==0) return 0; if(b&1) return ((1+quick(a,b/2+1,p)) * sum(a,b/2,p))%p; else return ((1+quick(a,b/2+1,p)) * sum(a,b/2-1,p) + quick(a,b/2,p))%p; } int main() { lom n,p,q; int t; cin>>t; while(t--) { cin>>q>>n>>p; cout<<(sum(q,n,p)-1)%p<<endl; } return 0; }