【fj夏令营】求和

2014年7月20日1,1310

【题目描述】

作为本场考试最水的一题,给定 n,k 和 m,请你计算: (1^k +2^k +3^k +…+n^k) mod m

【输入格式】

从 sum.in 中输入数据 一行,三个整数,n,k,m

【输出格式】

输出到 sum.out 中
一行,(1k +2k +3k +…+nk) mod m

【样例输入】

4 3 98

【样例输出】

2

【数据规模与约定】

数据规模

1 :n≤2^63 −1,k=1,m≤2^31 −1

2-3:n ≤ 10^6,k ≤ 100,m ≤ 10^7

4-5:n ≤ 10^8,k ≤ 10^7,m ≤ 3 ∗ 10^7

6-10:n ≤ 2^63 −1,k ≤ 2^63 −1,m ≤ 1.5∗10^6

题解

本题时限为2s。。。事实上标程极限数据正好卡过。。。

k=1直接等差数列求和

因为a^k%m=(a%m)^k%m,所以只需要算出1-min(n,m)的答案