记录编号	30201	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.070 s
提交时间	2011-10-28 08:05:20	内存使用	0.26 MiB

#include <fstream>
using namespace std;

long long pl(int num,int level,int moder)
{
	long long temp=1;
	while (level)
	{
		temp=(temp*num)%moder;
		level--;
	}
	return(temp);
}

int main(void)
{
	freopen("chashu.in","r",stdin);
	freopen("chashu.out","w",stdout);
	int i,n,temp,temp2,temp3;
	long long a[1001]={0,8},b[1001]={0,1};
	scanf("%d",&n);
	if (n==1) //只有一位时，需考虑n=0的情况
	{
		printf("9\n");
		fclose(stdin);
		fclose(stdout);
	}
	temp=10;
	for (i=2;i<=n;i++)
	{
		a[i]=((9*a[i-1])%12345+b[i-1])%12345; //为保证i位数满足条件，第i位填非3的数，则以前的数位必须保证是成立的，第i位填3，则以前的数位必须是不成立的
		temp2=temp; //temp2=10^(i-1)
		temp=pl(10,i,12345); //temp=10^i
		temp3=temp-temp2; //有temp3个i位数
		if (temp3<0)
			temp3+=12345;
		b[i]=temp3-a[i];
		if (b[i]<0)
			b[i]+=12345;
	}
	printf("%d\n",a[n]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}