描述
taozi喜欢数学,但是遇到数学题就头疼,zdragon为了让大家高兴高兴,给taozi出了道难题:
S=∑qi (1≤i≤n),由于答案可能会很大,答案对p取模。
输入
输入第一行为测试样例组数T(1≤T≤100)。
对于每组数据第一行包含三个正整数n,q,p(1≤n,q,p≤109)。
输出
对于每组数据,输出一个S对p取模的值。
样例输入
2
3 2 100
4 511 520
样例输出
14
184
提示
对于第一个样例,21+22+23=14,对100取模,答案为14。
分析:
首先想的是等比数列和Sn=a1(1-qn)/1-q,然后快速幂取模,但是由于里面有除法,行不通。
回到最开始的Sn=1+q+q2+...+qn,最后减掉1即可
当n为奇数时,Sn=(1+q+q2+...+qn/2)+(qn/2+1+...+qn)
提取q的n/2+1次方
Sn=(1+q+q2+...+qn/2)*(qn/2+1+1)
左边递归,右边快速幂
偶数的话qn另外算
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #define ll long long using namespace std; ll fastPow(ll n,ll p,ll mod){ ll base=p%mod; ll ans=1; while(n){ if(n&1) ans=(ans*base)%mod; base=(base*base)%mod; n>>=1; } return ans%mod; } ll sum(ll n,ll p,ll mod){ if(p==0)return 0; if(n==0)return 1; return (n&1)?(((1+fastPow(n/2+1,p,mod))%mod*sum(n/2,p,mod)%mod)%mod): (((1+fastPow(n/2,p,mod))%mod*sum(n/2-1,p,mod))%mod+fastPow(n,p,mod))%mod; } int main(){ int t; cin>>t; while(t--){ ll n,q,p; cin>>n>>q>>p; ll ans=sum(n,q,p); cout<<(ans+p-1)%p<<endl; } return 0; }View Code