链接:

题意：

Icebound hates math. But Imp loves math. One day, Imp gave icebound a problem.

The problem is as follows.

$\mathrm{S=(\sum ni=1qi） mod pS=(\sum i=1nqi） mod p\; For\; given\; q,n,p,\; you\; need\; to\; help\; icebound\; to\; calculate\; the\; value\; of\; S.}$

$\mathrm{思路：}$

$\mathrm{等比数列求和。}$

因为考虑到取余，所以不能直接算。

令S(n) 为等比数列前n项和。

若n为偶数：

　　S(n) = S(n/2) + S(n/2)*a^(n/2) (因为第i(i <= n/2)项和i+n/2项存在第i项乘a^(n/2)等以第i+n/2项的值。

若n为奇数：

　　S(n) = S(n/2) + S(n/2)*a^(n/2) + a^n

代码：

#include 
     
      using namespace std;typedef long long LL;LL n, q, p;LL QM(LL a, LL b, LL m){    LL res = 1;    while (b)    {        if (b&1)            res = (res*a)%m;        a = (a*a)%m;        b >>= 1;    }    return res;}LL GetR(int t){    if (t == 1)        return n%p;    if (t%2 == 0)        return (GetR(t/2)+(GetR(t/2)*QM(n, t/2, p))%p)%p;    else        return ((GetR(t/2)+(GetR(t/2)*QM(n, t/2, p))%p)%p+QM(n, t, p))%p;}int main(){    int t;    cin >> t;    while (t--)    {        cin >> n >> q >> p;        cout << GetR(q) << endl;    }    return 0;}