（高精度）NOJ-2287

Rank1_A
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 81920 KByte
总提交 : 25 测试通过 : 3
比赛描述

求n! (n的阶乘)在k进制下所有数位之和

输入
一行，两个十进制整数n,k; 0<=n<=1000,2<=k<=16

输出

一个十进制整数，为所求的结果

样例输入
5 10

样例输出
3

题目来源

NUPT

题解：用一个高精度乘除以及取余或者手写一个高精度乘法直接在每一次阶乘时计算出结果即可。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define MAXN 9999
#define MAXSIZE 1010
#define DLEN 4
class BigNum
{
	private:
		int a[1000]; //可以控制大数的位数
		int len;
	public:
		BigNum(){len=1;memset(a,0,sizeof(a));} //构造函数
		BigNum(const int); //将一个int类型的变量转化成大数
		BigNum(const BigNum &); //拷贝构造函数
		BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算
		BigNum operator*(const BigNum &)const; //重载乘法运算符，两个大数之间的相乘运算
		BigNum operator/(const int &)const; //重载除法运算符，大数对一个整数进行相除运算
		BigNum operator^(const int &)const; //大数的n次方运算
		int operator%(const int &)const; //大数对一个int类型的变量进行取模运算
		bool operator>(const BigNum &T)const;
		bool operator>(const int &t)const; //大数和一个int类型的变量的大小比较
};
BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
{
	int c,d=b;
	len=0;
	memset(a,0,sizeof(a));
	while(d>MAXN)
	{
		c=d-(d/(MAXN+1))*(MAXN+1);
		d=d/(MAXN+1);
		a[len++]=c;
	}
	a[len++]=d;
}
BigNum::BigNum(const BigNum &T):len(T.len) //拷贝构造函数
{
	int i;
	memset(a,0,sizeof(a));
	for(i=0;i<len;i++)
	a[i]=T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n) //重载赋值运算符，大数之间赋值运算
{
	int i;
	len=n.len;
	memset(a,0,sizeof(a));
	for(i=0;i<len;i++)
		a[i]=n.a[i];
	return *this;
}
BigNum BigNum::operator*(const BigNum &T)const //两个大数之间的相乘
{
	BigNum ret;
	int i,j,up;
	int temp,temp1;
	for(i=0;i<len;i++)
	{
		up=0;
		for(j=0;j<T.len;j++)
		{
			temp=a[i]*T.a[j]+ret.a[i+j]+up;
			if(temp>MAXN)
			{
				temp1=temp-temp/(MAXN+1)*(MAXN+1);
				up=temp/(MAXN+1);
				ret.a[i+j]=temp1;
			}
			else
			{
				up=0;
				ret.a[i+j]=temp;
			}
		}
		if(up!=0)
		ret.a[i+j]=up;
	}
	ret.len=i+j;
	while(ret.a[ret.len-1]==0 && ret.len>1)ret.len--;
	return ret;
}
BigNum BigNum::operator/(const int &b)const //大数对一个整数进行相除运算
{
	BigNum ret;
	int i,down=0;
	for(i=len-1;i>=0;i--)
	{
		ret.a[i]=(a[i]+down*(MAXN+1))/b;
		down=a[i]+down*(MAXN+1)-ret.a[i]*b;
	}
	ret.len=len;
	while(ret.a[ret.len-1]==0 && ret.len>1)
	ret.len--;
	return ret;
}
int BigNum::operator%(const int &b)const //大数对一个 int类型的变量进行取模
{
	int i,d=0;
	for(i=len-1;i>=0;i--)
	d=((d*(MAXN+1))%b+a[i])%b;
	return d;
}
bool BigNum::operator>(const BigNum &T)const //大数和另一个大数的大小比较
{
	int ln;
	if(len>T.len)return true;
	else if(len==T.len)
	{
		ln=len-1;
		while(a[ln]==T.a[ln]&&ln>=0)
		ln--;
		if(ln>=0 && a[ln]>T.a[ln])
			return true;
		else
			return false;
	}
	else
		return false;
}
bool BigNum::operator>(const int &t)const //大数和一个int类型的变量的大小比较
{
	BigNum b(t);
	return *this>b;
}

int n,k;

int main()
{
	scanf("%d%d",&n,&k);
	BigNum x=BigNum(1);
	for (int i=1;i<=n;i++)
	{
		x=x*BigNum(i);
	}
	int ans=0;
	while (x>0)
	{
		ans=ans+(x%k);
		x=x/k;
	}
	printf("%d\n",ans);
	return 0;
}