Project Euler 62

立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

MU-RI-YA-RI

#pragma comment(lib,"mpir.lib")
#include <iostream>
#include <deque>
#include <algorithm>
#include <mpir.h>
using namespace std;


// xを各桁ごとにばらしてdequeに挿入する。
deque<int> integerDigits(long long x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

deque<int> mpzIntegerDigits(const mpz_t& a){
	mpz_t x, tmp;
	mpz_init_set(x,a);
	mpz_init(tmp);
	int k, check;
	deque<int> arr;

	check = mpz_get_si(x);
	
	while( check!=0 ){
		// tmp = x%10;
		mpz_mod_ui(tmp, x, 10);

		k = mpz_get_si(tmp);

		arr.push_front(k);

		// x = x%10;
		mpz_div_ui(x,x,10);
		check = mpz_get_si(x);
	}

	return arr;
}


deque<int> makeNum(int n){
	mpz_t m;
	mpz_init_set_ui(m,n);
	mpz_mul_ui(m,m,n);
	mpz_mul_ui(m,m,n);

	deque<int> d = mpzIntegerDigits(m);
	sort(d.begin(), d.end());
	return d;
}


int main(){
	const int MAX_N = 10000;

	for(int i=1 ; i<MAX_N ; i++){
		if(i%100==0) cout << i << endl;

		deque<int> di = makeNum(i);
		for(int j=i+1 ; j<MAX_N ; j++){
			deque<int> dj = makeNum(j);

			if(di.size() < dj.size()) break;
			if(di!=dj) continue;

			for(int k=j+1 ; k<MAX_N ; k++){
				deque<int> dk = makeNum(k);

				if(di.size() < dk.size()) break;
				if(di!=dk) continue;

				for(int l=k+1 ; l<MAX_N ; l++){
					deque<int> dl = makeNum(l);

					if(di.size() < dl.size()) break;
					if(di!= dl) continue;

					for(int m=l+1 ; m<MAX_N ; m++){
						deque<int> dm = makeNum(m);

						if(di.size() < dl.size()) break;
						if(di!=dm) continue;

						cout << i << " " << j << " " << k << " " << l << " " << m << endl;

					}
				}
			}
		}
	}
	cout << "end" << endl;

	int end;
	cin >> end;
}