n자리 숫자이면서 n제곱수도 되는 양의 정수는 모두 몇 개?

[eng][kor]

이 문제에서 풀려야 할 것들은 다음과 같다.

1) n의 상한선은 어디까지?

2) 몇 제곱까지 계산할 경우 의미가 있는지?

3) 큰 수도 다룰 수 있는지?


이에 대한 답.

-n이 10보다 클 경우, n을 제곱하면 무조건 n자리보다 크기 때문에 n은 9 이하의 수여야 한다.

-제곱을 해보다가 n자리 숫자가 안 되면, 그 다음 제곱부터도 어차피 n자리 수를 만들 수 없다.

-언어에서 큰 수를 지원하면 좋고 아니면 큰 수를 다룰 도구 코드가 필요하다.


실행시간 0.003 초. 여기에는 메인 코드만 올린다. 메인에서 호출하는 큰 수 클래스 구현 코드는 오일러 57 에서 썼던 코드를 가져왔고, 길어져서 여기에 안 올리고 깃헙 링크로만 남겨둔다. 큰 수 클래스는 쓰면서 군데군데 불편함을 느꼈는데, 귀찮아서 아직 고치지 않고 그냥 쓰는 중.

/*
 	Problem 63 - Powerful digit counts
*/
	
#include <iostream>
#include <ctime>
#include <math.h>
#include <string.h>

#include "BigInt.h"

using namespace std;
int main(int argc, char** argv)
{
	clock_t begin = clock();
	/* starting code */

	int cnt = 1; // 1^1
	int prev_ilen = 1;

	unsigned long int i=2;
	while( i < 10)
	{
		for(int j=1; ; j++)
		{
			BigInt powed = BigInt(1);
			for(int k=0; k<j; k++) { 
				BigInt operand(i);
				powed = powed * operand;
			}
			cout << endl;
			
			int digitlen = powed.getDigitsLen();
			if( digitlen == j) {
					cnt++;
					cout << "i=" << i << " j=" << j << " powed="; powed.print(); cout << " cnt=" << cnt << endl;
			}
			if( digitlen < j) break;
		}
		i++;
	}

	cout << "cnt=" << cnt << endl;

	/* end of code */
	clock_t end = clock();
	std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
	return 0;
}