|poj 1995|快速幂|Raising Modulo Numbers

poj传送门

根据题目公式

(AB11+AB22+...+ABhh)modM 快速幂即可

#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ms(i,j) memset(i,j, sizeof i); using namespace std; #define ll long long int h; ll m; ll ans; ll poww(ll a, ll b) { ll ans = 1, base = a%m; while (b!=0) { if (b&1!=0) { ans = (ans*base)%m; } base = (base*base)%m; b>>=1; } return ans; } int main() { int kase; scanf("%d", &kase); while (kase--) { scanf("%lld%d", &m, &h); ans = 0; for (int i=1;i<=h;i++) { ll a,b; scanf("%lld%lld", &a, &b); ans = (ans+poww(a,b))%m; } printf("%d\n", ans%m); } return 0; }