poj 1995 整数快速幂模m

2019-04-14 21:30发布

站内文章 / 模拟电子
14102 0 1625
题意：做codeforces碰到的矩阵快速幂，学的过程中顺便学学这种二分幂的方法。题意就是求ai^bi进行累加和，最后模m。 思路：将幂转化成二进制来算。 #include #include using namespace std; int main() { long long Z , M , H , a , b; scanf("%lld",&Z); while (Z--) { scanf("%lld",&M); scanf("%lld",&H); long long ans , sum = 0; for(int i = 0 ; i < H ; i ++) { scanf("%lld%lld",&a,&b); ans = 1; while(b) { //b转化成二进制 if (b&1) { //最后一位是1的情况才处理 ans = (ans*a)%M; b--; } //最后一位不是1的情况只是算出当前位的a^2^i即可 b/=2; a = (a*a)%M; //a的2的i次方 等于a的2的i-1次方的平方 把所有的a^2^i列举出来 } sum += (ans%M); } printf("%lld ",sum%M); } }