【HBUOJ】暴躁的阿生

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/shiliang97/article/details/100562555

暴躁的阿生

Description

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

图片.png

，对于给定的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;
}