【数论】等比数列求和取模

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 9
#define mod 9901
using namespace std;
// Notice the data size
// Notice the input and output 

LL n,m,k;
LL p[MS];

LL qpow(LL n ,LL m){
	LL ans = 1%mod;
	for(;m;m>>=1){
		if(m&1) ans = ans*n%mod;
		n = n*n%mod;
	}
	return ans;
}

LL calc(LL n ,LL m){ // 1+n+n^2+...+n^m;
	if(m == 0) return 1;
	else if(m&1) return (1+qpow(n,(m+1)/2))*calc(n,m/2)%mod;
	else return ((1+qpow(n,m/2))*calc(n,m/2-1)%mod+qpow(n,m))%mod;
}

int main(){
	ios::sync_with_stdio(false);
	LL a1 ,q ,tot; // 首项 ,公比 ,项数
	cin >> a1 >> q >> tot;
	tot--;
	cout << a1*calc(q,tot)%mod << endl; 
	
	
	return 0;
}