题目描述

给定3个整数A,K,P，求 $ (A^1 + A^2 + … + A^K) mod P $ 的结果

数据范围

$ 0<= A <= 10^8, 0< K <= 10^{16}, 0 < P <= 10^8 $

思路

$ S=(A^1 + A^2 + … + A^K) mod P $

1. 当$k\%2==1$时,$S=(1+A^{K/2}) \times (A^1 + A^2 + … + A^{K/2})+A^K$
2. 当$k\%2==0$时,$S=(1+A^{K/2}) \times (A^1 + A^2 + … + A^{K/2})$

代码实现

#include <bits/stdc++.h>
using namespace std;

long long b,n,k;

long long po(long long b,long long n){
    long long ans=1,t=b%k;
    while (n){
        if (n&1){
            ans=(ans*t)%k;
        }
        t=(t*t)%k;
        n>>=1;
    }
    return ans;
}

long long add(long long r){
    if (r==1) return b%k;
    if (r&1){
        return (po(b,r)+add(r-1))%k;
    }else{
        return ((1+po(b,r/2))*add(r/2))%k;
    }
}

int main(){
    cin>>b>>n>>k;
    cout<<add(n)%k;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

long long a,k,p,s=1,ans,t;

long long po(long long m){
    long long tta=a,ans=1;
    while (m>0){
        if (m%2==1) ans=ans*tta%p;
        m/=2;
        tta=tta*tta%p;
    }
    return ans;
}

long long pow(long long m){
    if (m<=0) return 1;
    if (m==1) return a%p;
    long long ta=1;
    ta=ta*(po(m/2)+1)%p;
    ta=ta*pow(m/2)%p;
    if (m%2==1) {
        ta=(ta+po(m))%p;
    }
    m/=2;
    return ta;
}

int main(){
    cin>>a>>k>>p;
    ans=pow(k);
    cout<<ans;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/44/