【等比数列二分求和】tzoj 桃子的难题

描述

taozi喜欢数学,但是遇到数学题就头疼,zdragon为了让大家高兴高兴,给taozi出了道难题:

S=∑q(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另外算

【等比数列二分求和】tzoj 桃子的难题
#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

 

 

上一篇:均值不等式


下一篇:黄金分割比