暴躁的阿生

Description

 

阿生最近迷上了解数学题，其中有一道题是这样的：

，对于给定的q,n,p，需要计算S的值，阿生无论如何也解不出来，这导致阿生内心极其崩溃。为了防止阿生做出出格的举动，大家快帮帮他吧

Input

 

输入包含三个整数，q,n,p       1<= q,n,p <=10^9;
 

Output

 

输出S的值

Sample Input 1 

2 3 100

Sample Output 1

14

Sample Input 2 

511 4 520

Sample Output 2

184

 

又是一道因为没有人AC而降低测试点的题?

求幂有一个 快速幂的算法，我只是知道，但我不会写

✍

我直接就粘贴过来模板了

int quickPow(int a,int b,int m){
    int sum=1;
    while(b){
        if(b&1) sum=sum*a%m;
        b>>=1;
        a=a*a%m;
    }
    return sum;
}

AC答案

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,m;
int quickPow(int a,int b,int m){
    int sum=1;
    while(b){
        if(b&1) sum=sum*a%m;
        b>>=1;
        a=a*a%m;
    }
    return sum;
}
int main(){
    scanf("%d%d%d",&a,&b,&m);
    int sum=0;
    for(int i=1;i<=b;i++){
    	sum+=quickPow(a,i,m);
    	//cout<<sum;
	}
    printf("%d\n",sum%m);
    return 0;
}