#P52033. 「LOJ」 自然数幂之和
「LOJ」 自然数幂之和
题目描述
给出 次询问和一个模数 ,每次询问给出两个正整数 ,需要求出 的值。
需要注意, 不一定为质数。
输入格式
共 行。
第一行读入两个正整数 。
接下来的 行,每行读入两个正整数 ,表示该次询问需要求出 。
输出格式
共 行。
第 行输出一个非负整数,表示第 次询问的答案。
样例
10 2
2 5
3 3
3
6
数据范围与提示
对于 的数据,满足 。
不保证模数 为质数。
给出 m 次询问和一个模数 P,每次询问给出两个正整数 n,k,需要求出 S(n,k)=∑i=1nikmodP 的值。
需要注意,P 不一定为质数。
共 m+1 行。
第一行读入两个正整数 P,m。
接下来的 m 行,每行读入两个正整数 n,k,表示该次询问需要求出 S(n,k)。
共 m 行。
第 i 行输出一个非负整数,表示第 i 次询问的答案。
10 2
2 5
3 3
3
6
对于 100% 的数据,满足 1≤m≤50,1≤P≤109,1≤n≤109,1≤k≤104。
不保证模数 P 为质数。