「fj夏令营」求和

2014年7月20日3,1010

「题目描述」

作为本场考试最水的一题,给定 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)的答案

 

avatar
  Subscribe  
提醒