桁数が大きな数字を計算する方法

Question

以下の問題がわかりません。

---

正整数 n ( 0 < n < 80 ) に対して, n桁以内の最大の３のベキ乗数を左詰めで書き出すプログラムを作れ。

【入力】
正整数 n ( 0 < n < 80 ) １つ。

【出力】
１行として書き出す（末尾に改行を書き出すこと）。

【例】
入力１
1
出力１
9

入力２
6
出力２
531441

---

以下のようなコードを書いて実行したところ、nが小さいときはうまくいくのですが、大きくなると0と出力されてしまいます。
試しにn=60で調べてみたところ、for文の中でi=8まではmaxの値は正しかったのですが、n=9以降で明らかに10の累乗ではない値が出始め、i=31以降はずっとmax=0となっていました。
やり方が根本的に違うのかと思いますが、どなたかご教授くださると助かります。
よろしくお願いいたします。

#include<stdio.h>
#include<math.h>

int main(void){
    int i,n,ans=1,max=1;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        max=max*10;        
    }
    while(ans<max){        
        ans=ans*3;
    }
    printf("%d\n",ans/3);
    return 0;
}

Answer 1

とりあえず、作ってみました。

char 型のバッファを使っていますが、
各くバイトには 0 - 9 の範囲の値をとる形にしています。

#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>

#define	MIN_N_FIG				(0)
#define	MAX_N_FIG				(80)

//
// バッファ上の数値を 10進数 演算で加算する
// a = a + b;
//
void							StrAdd(char *a, char const * b)
{
	size_t						i;
	int							cy;
	int							wk;
	char *						org_a;

	org_a = malloc(MAX_N_FIG);
	memcpy(org_a, a, MAX_N_FIG);

	cy = 0;
	for (i = 0U; i < MAX_N_FIG; i++) {
		wk = *(org_a + i) + *(b + i) + cy;
		*(a + i) = wk % 10;
		cy = wk / 10;
	}
	free(org_a);
}

//
// バッファ上の数値を 10進数 演算で 3倍する
// a = a * 3;
//
void							StrMul3(char *a)
{
	char *						org_a;

	org_a = malloc(MAX_N_FIG);
	memcpy(org_a, a, MAX_N_FIG);
	StrAdd(a, org_a);
	StrAdd(a, org_a);
	free(org_a);
}


//
// バッファ上の数値を 表示
//
void							StrPrt(char const * a)
{
	size_t						i;
	int							bFirstDt;

	bFirstDt = 0;
	for (i = MAX_N_FIG; 0 < i; i--) {
		if (*(a + i - 1) != 0) {
			bFirstDt = 1;
		}
		if (bFirstDt != 0) {
			printf("%c", *(a + i - 1) + '0');
		}
	}
	printf("\n");
}

int								main(void)
{
	int							n;
	char						buf[2 + 1];
	char						Cbf[MAX_N_FIG];
	char						Cwk[MAX_N_FIG];

	printf("N を入力して下さい ==> ");
	fgets(buf, sizeof(buf), stdin);
	n = atoi(buf);
	if (MIN_N_FIG < n  && n < MAX_N_FIG) {
		memset(Cbf, 0, sizeof(Cbf));
		memset(Cwk, 0, sizeof(Cwk));
		Cbf[0] = 1;
		while (1) {
			memcpy(Cwk, Cbf, MAX_N_FIG);
			StrMul3(Cbf);
			if (Cbf[n] != 0) {
				break;
			}
		}
		StrPrt(Cwk);
	}
	else {
		printf("N は %d < N < %d の範囲でなくてはなりません。\n", MIN_N_FIG, MAX_N_FIG);
	}
	return(0);
}

Comments

[haru-1218]

ありがとうございます！大変助かりました。

Answer 2

この質問見覚えあるのですが

Comments

[y_waiwai]

まあ、講習なんかでよく出される問題っちゃーそーですねｗ

[Zuishin]

よく出されるどころではなく、一字一句同じですね。

Answer 3

gmpつかったら? https://euniclus.com/article/c-language-gmp-big-multiple-long-integer/

Answer 4

10進で80桁となると2進数で260桁以上すなわち260bit以上でないと。
intで32bitなので到底無理。