今天啊，真的是太恶心了，第一题就是数论。唉，确认过眼神，是我不会AC的题目，不过值得庆幸的是，第一题有50分可以用暴力打出来，然后第二题的话我勉强拿了个15分，至少没有爆零，我已经知足了。
第一题题意大概是这样的，给你三个数k,n,p。我们要求的答案差不多是（k^(n-1)-1）/(n-1)%p。不过呢，我没用这个方法，因为我根本就不会！这个题目的k<=2的31次方，n<=1e18。十分恶心（反正恶心到我了）。这题用时间复杂度为根号n的算法都会爆，所以就要优化他，然后啊，我就是不会优化，然后被迫打暴力。
接下来上题解，题面照片也上来。
然后是题解：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll k,p,ans;
unsigned long long n;
ll pow(ll a,ll b,ll p){
int ret=1;
while(b){
if(b&1)
ret=reta%p;
a=aa%p;
b>>=1;
}
return ret;
}
ll pfc(ll a,ll Log,ll p){
ll ret=1;
while(Log–){
ret=ret*(a+1)%p;
a=a*a%p;
}
return ret;
}
int main()
{
freopen(“split.in”,“r”,stdin);
freopen(“split.out”,“w”,stdout);
scanf("%lld%lld%lld",&k,&n,&p);
n–;
unsigned long long Log;
while(n){
for(Log=0;1ll<<Log<=n&&Log<64;Log++);
Log–;
n-=(1ll<<Log);
ans=(ans+pfc(k,Log,p)*pow(k,n,p))%p;
}
printf("%lld\n",ans);
}
是由我在其他人的博客理解然后自己按着打一遍的，在这里特别谢谢博主，以下是那位博主关于这道题的讲解写的博客。
https://blog.csdn.net/outer_form/article/details/49047081