记录编号	189711	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008] 越狱	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-09-29 10:24:32	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
using namespace std;
//result = (m%100003)^n %(100003) - m*(m-1)^(n-1)%100003
//a^(2n)%c = (a^n%c)^2%c
// a*b % c = a%c * b%c  %  c
//a^(2n+1)%c = a^n * a^n *a  %  c  = (a^n%c)^2%c * a%c   % c
long long m;
long long resulta(long long n){
	if(n==1)
		return m;
	else if(n&1){
		long long r = resulta(n/2);
		r *= r;
		r %= 100003;
		r = r*m%100003;
		return r;
	}else{
		long long r = resulta(n/2);
		r *= r;
		r %= 100003;
		return r;
	}
 
}
long long resultb(long long n){
	m--;
	return resulta(n-1)*(m+1)%100003;
}
int main(){
	freopen("prisona.in","r",stdin);
	freopen("prisona.out","w",stdout);
	long long n;
	cin>>m>>n;
	m%=100003;
	int a = resulta(n),b = resultb(n);
	if(a>b)cout<<a-b;
	else cout<<100003+a-b;
 	fclose(stdin);fclose(stdout);
	return 0;
}