poj 1995 Raising Modulo Numbers【快速幂】

梦里梦外; 2022-08-09 01:50 7阅读 0赞

Raising Modulo Numbers

Input

The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 <= M <= 45000). The sum will be divided by this number. Next line contains number of players H (1 <= H <= 45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time.

Output

For each assingnement there is the only one line of output. On this line, there is a number, the result of expression.

(A1B1\+A2B2\+ ... +AHBH)mod M.

题目大意：数入一个数，表示样例个数，每个样例第一行输入M【即公式中的那个M（除数）】，然后第二行输入一个n，表示接下来n行，每一行输入一对*Ai*  B*i*，

求*(A1B1\+A2B2\+ ... +AHBH)mod M的值。*

Sample Input

3
    16
    4
    2 3
    3 4
    4 5
    5 6
    36123
    1
    2374859 3029382
    17
    1
    3 18132

Sample Output

2
    13195
    13

已Accept代码【c++提交】

#include <cstdio>
    #include <cstring>
    using namespace std;
    typedef long L;
    int n, m;
    
    int PowerMod(int a, int b) {		//快速幂模板 
    	L res = 1;
    	a = a % m;
    	while(b > 0) {
    		if(b & 1)
    			res = (res * a) % m;
    		a = (a * a) % m;
    		b >>= 1;					//位运算 相当于b = b / 2; 
    	}
    	return res;
    }
    
    int Scanf_a() {
    	int a, b, c;
    	scanf("%d%d", &m, &n);
    	scanf("%d%d", &a, &b);
    	c = PowerMod(a, b);
    	for(int i = 1; i < n; i++) {
    		scanf("%d%d", &a, &b);
    		c = (c + PowerMod(a, b)) % m;
    	}
    	return c;
    }
    
    int main() {
    	int t;
    	scanf("%d", &t);
    	while(t--) {
    		printf("%d\n", Scanf_a());
    	}
    	return 0;
    }