原题链接

题目大意

对于给定的n，p，q，求$(\sum_{i=1}^n{q^i}) mod   p$
简单来说就是等比数列求和取余

解题思路

  • 很自然的想到用等比数列求和公式$$Sum=a_1*\frac{1-q^n}{1-q}=\frac{q^{n+1}-q}{q-1} mod p$$

    由同余定理可知这样做的难点就是将除法转化为乘法，也就是求$q-1$对模$p$时的逆元，但是题目所给数据无法保证$gcd(q-1,p)=1$,所以逆元不一定存在。
    (关于求逆元的博客日后补上待填坑)
    可以利用公式$$a/b \space mod\space c = a \space mod\space(b*c)\space/b$$
    可将求和公式转化为$$Sum=(q^{n+1}+q)\space mod \space [p*(q-1)] \space /(q-1)$$

  • 分治的思想

    首先可以考虑$n$为偶数的情况，$$Sum = (\sum_{i=1}^n{q^i}) mod   p =(q+q^2+q^3+…+q^n) mod  p$$
    $$=(q+q^2+…+q^{\frac{n}{2}})+q^{\frac{n}{2}}*(q+q^2+…+q^{\frac{n}{2}}) mod p$$

    $$=(1+q^{\frac{n}{2}})*(q+q^2+…+q^{\frac{n}{2}})  mod   p$$
    这样就将问题转化为了求$1—\frac{n}2$的等比数列求和

    定义函数$f(q,n)$表示首项、公比都为$q$的等比数列前$n$项的和,那么就有$$f(q,n)=f(q,\frac{n}{2})*(1+q^{\frac{n}{2}})$$
    递归求解即可

    对于n为奇数的情况:$$f(q,n)=f(q,n-1)+q^n$$
    时间复杂度$O(logn*logn)$

  • 矩阵快速幂

    因为等比数列的递推公式也是线性的，所以可以构造矩阵行列式+矩阵快速幂来求解
    $$a_{n+1}=q*a_{n}\\q=q$$

    $$
    \begin{pmatrix}
    a_{n+1}\\
    q
    \end{pmatrix}
    =\begin{pmatrix}
    q&0\\
    0&1
    \end{pmatrix}
    *\begin{pmatrix}
    a_{n}\\
    q
    \end{pmatrix}
    $$
    所以可以推得
    $$\begin{pmatrix}a_{n}\\q\end{pmatrix} = {\begin{pmatrix}q&0\\0&1\end{pmatrix}}^{n-1} * \begin{pmatrix}a1\\q\end{pmatrix}$$

AC代码

分治法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mod,n,q;
int T;

ll mod_pow(ll x,ll n,ll mod) 
{
    ll res=1;
	x%=mod;
    while(n>0)
    {
        if(n&1)res= res * x%mod;
        
        x=x*x%mod;   
        
        n>>=1;      
    }
    
    return res;
}

ll get_ans(ll qq,ll nn)
{
	if(nn==1)return qq;
	else if(nn==0)return 1;

	if(nn&1)
	{
		return (get_ans(qq,nn>>1)*(1+mod_pow(q,nn>>1,mod))+mod_pow(q,nn,mod))%mod;
	}
	else {
		return ((get_ans(qq,nn>>1)*(1+mod_pow(q,nn>>1,mod)))%mod);
	}
}

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>q>>n>>mod;
		
		cout<<get_ans(q%mod,n)<<endl;
	}
}