记录编号	77815	评测结果	AAAAAAAAAA
题目名称	方程	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-11-02 18:24:53	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<vector>
using namespace std;
const int MOD=1000;
const int SIZEL=1000;
const int SIZEP=1000;
int K,X;
class HPINT{
public:
	int len;
	int s[SIZEL];
	HPINT(){
		memset(s,0,sizeof(s));
	}
	void mul(int);
	void assign_one(void){
		len=1;
		s[0]=1;
	}
	void output(void){
		int i;
		for(i=len-1;i>=0;i--) printf("%d",s[i]);
	}
};
void HPINT::mul(int x){//*=x
	int i;
	for(i=0;i<len;i++) s[i]*=x;
	for(i=0;i<len||s[i];i++){
		s[i+1]+=s[i]/10;
		s[i]%=10;
	}
	len=max(len,i);
	while(!s[len-1]) len--;
}
int quickpow(int a,int n){
	int ans=1;
	while(n){
		if(n&1) ans*=a,ans%=MOD;
		a*=a,a%=MOD;
		n>>=1;
	}
	return ans%MOD;
}
bool flag[SIZEP+1]={1};//值为false代表它是素数
vector<int> prime;
void getprime(void){
	int i,j;
	int high=(int)sqrt((double)SIZEP);
	for(i=2;i<=high;i++){
		if(!flag[i]){
			for(j=i*i;j<=SIZEP;j+=i){
				flag[j]=true;
			}
		}
	}
	for(i=2;i<=SIZEP;i++) if(!flag[i]) prime.push_back(i);
}
void init(void){
	cin>>K>>X;
	X%=MOD;
	X=quickpow(X,X);
}
void getfact(int x,int p[]){//将x质因数分解,p中加上相应的指数
	int i;
	for(i=0;i<prime.size();i++){
		while(x%prime[i]==0){
			p[prime[i]]++;
			x/=prime[i];
		}
		if(x<=1) return;
	}
}
HPINT C(int n,int m){//n取m的高精
	int mol[SIZEP+1]={0},den[SIZEP+1]={0};//分子和分母的各素因子指数
	int i;
	for(i=n-m+1;i<=n;i++) getfact(i,mol);//分子
	for(i=1;i<=m;i++) getfact(i,den);
	for(i=1;i<=SIZEP;i++) mol[i]-=den[i];
	HPINT ans;
	ans.assign_one();
	int j;
	for(i=1;i<=SIZEP;i++){
		if(mol[i]){
			for(j=1;j<=mol[i];j++) ans.mul(i);
		}
	}
	return ans;
}
void work(void){
	HPINT ans=C(X-1,K-1);
	ans.output();cout<<endl;
}
int main(){
	freopen("equationz.in","r",stdin);
	freopen("equationz.out","w",stdout);
	getprime();
	init();
	work();
	return 0;
}