【NOIP模拟赛】calc

2014年11月6日1,6360

题目说明

给三个正整数n,m和p,求(n^1+…n^m) mod p。

输入格式

一行,三个整数n,m和p。

输出格式

输出答案。

样例

Sample Input

2 2 5

Sample Output

1

数据范围

n,p<=10^8 m<=10^17

相关信息

文件名: calc.pas/c/cpp

输入文件: calc.in

输出文件: calc.out

时限: 1s

空间限制: 64MB

题解

暴力直接快速幂

正解应该是矩阵乘法

然后我作死试图用数论。。。逆元没学好

根据等比数列求和公式得到(省略)/(n-1) mod p

发现n-1和p可能不互质,然后(省略)/(n-1) 和 p 都乘上gcd,最后答案除以gcd

这样就能用乘法逆元算了

假设数据这样乱搞不会爆longlong