简单的组合数论问题

Question

集合｛4^n｝（0＜＝n＜＝k（k为给定的正整数）中首位为i的有多少个（i＝1，2，3，4，5，6，7，8，9）？
用k的表达式表示。
（最好用a进制或生成函数方法）

Answer 1

用a进制方法不知道是什么意思....
生成函数对这道题不知道怎么用...
所以只好用原始方法..

验算一下n从0到20，发现首位的规律似乎是1，4，1，6，2的循环
但是4的23次方等于70368744177664，首位是7。

所以问题好象很麻烦.....我只想出下面这个方法....

#include <stdio.h>
#define MAX_LENTH 1000
#define BASE 4
//可以计算到4的1660次方，
//如果要增大范围只要增大MAX_LENTH就可以了
void calculate(int n)
{
int total[10]={0};
int i,place,carry,tmp;
int num[MAX_LENTH];
num[0]=1;

for(i=1;i<MAX_LENTH;i++)num[i]=-1;
printf("0\t:\t1\n");
total[1]++;
for(i=1;i<=n;i++){
carry=0;
for(place=0;num[place]!=-1&& place<MAX_LENTH ;place++)
{
tmp = num[place] * BASE + carry ;
num[place] = tmp % 10 ;
carry = tmp / 10;
}
if(carry!=0)
{
if(place==MAX_LENTH)
{
printf("\n\nwarning:\noverflow\n\n");
break;
}
else
{
num[place]=carry;
total[carry]++;
}
}
else //carry==0
{
total[num[--place]]++;
}

//打印每个次方
printf("%d\t:\t",i);
for( ; place>=0 ; place--)
printf("%c",num[place]+'0');
printf("\n");

}
//打印总次数
printf("total times:\n");
for(i=1;i<=9;i++)
{
printf("%d : %d\n",i,total[i]);
}
printf("\n\n");
}

main()
{
int n;
while(printf("Please enter n:"),
scanf("%d",&n),
n>=0)
{
calculate(n);
}
}

希望对你有帮助。。。