프로젝트 오일러 48
projecteuler, cpp처럼 큰 수라도 의미가 있는 부분은 마지막 10자리 결과값이다. 그리고 큰 수에 대한 사칙연산 코드는 예전의 문제를 풀면서 몇 번 만들어 보았다.
오일러 20번에서의 큰 수 곱셈 코드로 power를 구하는 함수를 짤 수 있고, 오일러 25번에서의 큰 수 덧셈코드를 가져왔다. 실행시간 0.463초.
/*
Problem 48 - Self Powers
*/
#include <iostream>
#include <ctime>
#include <cmath>
#include <string.h>
#include <stdio.h>
using namespace std;
void multiply( int result[], int mul, int maxlen)
{
for(int i=0; i<maxlen; i++)
{
//cout << "i=" << i << " carry=" << carry << endl;
//int val = result[i] * mul;
result[i] = result[i] * mul;
}
// trim
int nextcarry = 0;
for(int i=0; i<maxlen; i++)
{
int carry = nextcarry;
nextcarry = result[i]/10;
result[i] = result[i]%10 + carry;
while( result[i]>=10) {
result[i] = result[i]-10;
nextcarry++;
}
}
}
int toint( int result[], int size)
{
int toint = 0;
for(int i=0; i< size; i++)
{
toint += pow(10, i) * result[i];
}
return toint;
}
void bigpow( int result[], int exponent, int stopat)
{
int i = toint(result, stopat);
while( exponent-1)
{
multiply( result, i, stopat);
exponent--;
}
}
void sum( int dst[], int src[], int max)
{
for(int i=0; i<max; i++)
{
dst[i] += src[i];
if( dst[i] >= 10) {
if(i+1 < max) {
dst[i+1] += dst[i]/10;
}
dst[i] = dst[i]%10;
}
}
}
using namespace std;
int main(int argc, char** argv)
{
clock_t begin = clock();
/* starting code */
int result[10]= {0,};
for(int i=1; i<=1000; i++)
{
cout << "i=" << i << endl;
int buf[10] = {0,};
char cbuf[10] = {0,};
sprintf( cbuf, "%d", i);
int slen = strlen( cbuf);
for(int c=slen; c>0; c--)
{
buf[ slen-c] = cbuf[c-1]-'0';
}
bigpow( buf, i, 10);
sum( result, buf, 10);
}
cout << "sum=";
for(int i=9; i>=0; i--)
{
cout << result[i];
}
cout << endl;
/* end of code */
clock_t end = clock();
std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
return 0;
}