HOJ 2901 Calculation 快速幂裸模板题

http://acm.hit.edu.cn/hoj/problem/view?id=2901

HOJ 2901 Calculation

My Tags	快速幂   (Edit)

	Source : GTmac
	Time limit : 1 sec		Memory limit : 32 M

Submitted : 312, Accepted : 105

Given two integers a and b, you are to calculate the value of the following expression: (1^b + 2^b + ... + a^b) modulo a.

Note that b is an odd number.

Input specifications

Each line of input consists of two integers a and b (1≤a≤1000000000, 1≤b≤1000000000) respectively.

Output specifications

For each case of input, you should output a single line, containing the value of the expression above.

Sample Input

1 1
2 1

Sample Output

0
1

/*
* 题目：
*　　 ( 1^b + 2^b + ... + a^b ) % a
* 分析：
* 　　我们可以发现 a | [ i^b + (a-i)^b ]，所以当a为奇数的时候可以直接快速幂，偶数的时候为0 
*
* */

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

ll cal(ll a,ll b,ll mod){
	ll res = 1;
	while(b>0){
		if(b&1)
			res = res*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return res;
}

int main(){
	ll a,b;
	while(cin>>a>>b){
		if(a&1)
			puts("0");
		else
			cout<<cal(a/2,b,a)<<endl;
	}
	return 0;
}