简单的组合数论问题

来源：百度知道 编辑：UC知道 时间：2024/06/20 15:14:14
集合｛4^n｝（0＜＝n＜＝k（k为给定的正整数）中首位为i的有多少个（i＝1，2，3，4，5，6，7，8，9）？
用k的表达式表示。
（最好用a进制或生成函数方法）

用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
{