洛谷 P1630 求和

给一个式子，求它的值，(1^b+2^b+...+a^b)%1e4

输入格式

第一行一个数t，表示有t组测试数据

对于每组测试数据，一行有两个整数a,b

部分数据：1<=t<=10, a,b<=1e3

对于100%的数据,1<=t<=100,1<=a,b<=1e9

输出格式

共t行，每行一个整数

输入/输出例子1

输入：

1

2 3

输出：

9

样例解释

无

取模的值通常是有规律的，模范围非常小可以通过找规律来解决

指数很大我们可以用快速幂来解决，再逆天的数都可以在64次内解决（即O（1））。

所以b很大不是问题（逃），问题是a这么大如何解决，这样一个循环肯定是要爆的。

取模的值通常是有规律的，而且这道题给的模范围非常小，也就是说可以通过找规律来解决

原式：a^b % p

即：b个a相乘再模上p，下面用2个a来代替b个a

转换：

(a*a) % p 通过乘法取模分配律得到下面的式子

(a%p * a%p)%p （也就是b个a%p相乘再模p）

(a%p)^b % p

也就是a的范围被p限制住了，若p=100，那么a=101 相当于 a=1

所以这道题写一个前缀和就做出来了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5, Mod=1e4;

int t, a, b, sum[N];
int Pow(int a, int b)
{
	if (b==1) return a%Mod;
	
	int t=Pow(a, b/2);
	if (b%2==0) return (t%Mod*t%Mod)%Mod;
	else return (t%Mod*t%Mod*a%Mod)%Mod;
} 
signed main()
{
	scanf("%lld", &t);
	while (t--)
	{
		scanf("%lld%lld", &a, &b);
		for (int i=1; i<=10000; i++) sum[i]=(sum[i-1]+Pow(i, b))%Mod;
		
		printf("%lld\n", (a/10000*sum[10000]%Mod+sum[a%10000]%Mod)%Mod);
	}
	return 0;
}