Project Euler 55

47とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.

全ての数が素早く回文数になるわけではない. 349を考えよう,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
349は, 3回の操作を経て回文数になる.

まだ証明はされていないが, 196のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数で無いと証明されていない数はLychrel数だと仮定する.

更に, 10000未満の数については以下を仮定してよい.

50回未満の操作で回文数になる
まだ誰も回文数まで到達していない
実際, 10677が50回以上の操作を必要とする最初の数である: 4668731596684224866951378664 (53回の操作で28桁のこの回文数になる).

驚くべきことに, 回文数かつLychrel数であるものが存在する. 最初の数は4994である.

10000未満のLychrel数の個数を答えよ.

C/C++

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

deque<int> mpzIntegerDigits(mpz_t*);
void mpzFromDigits(mpz_t*, deque<int>);
deque<int> deqReverse(deque<int>);
string mpzToString(mpz_t*);
bool mpzIsPalindromic(mpz_t*);
void mpzPalindromicAdd(mpz_t*, mpz_t*);
bool isLychrel(int);



// xを各桁ごとにばらしてdequeに挿入する。(mpir版)
deque<int> mpzIntegerDigits(mpz_t* x){
	deque<int> arr;
	mpz_t tmp;
	int k, check;
	string str;
	char chr[10000];

	// xの値をchrに退避
	str = mpzToString(x);
	strcpy_s(chr, str.c_str());

	mpz_init(tmp);
	check = mpz_get_si(*x);

	while( check!=0 ){
		//tmp = x%10;
		mpz_mod_ui(tmp, *x, 10);
		
		//tmpの値をintにして取り出す
		k = mpz_get_si(tmp);

		arr.push_front(k);

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

	//xの値をsetし直す
	mpz_set_str(*x, str.c_str(), 10);

	return arr;
}

// integerDigitの逆(mpir版)
void mpzFromDigits(mpz_t* x,deque<int> arr){
	mpz_set_ui(*x,0);

	while(!arr.empty()){
		mpz_mul_ui(*x, *x, 10);
		mpz_add_ui(*x, *x, arr[0]);
		arr.pop_front();
	}
}

// dequeの順番を逆にする。(stlとかにありそう・・・)
deque<int> deqReverse(deque<int> arr){
	deque<int> ret;
	while(!arr.empty()){
		ret.push_back(arr.back());	
		arr.pop_back();
	}
	return ret;
}

// mpz_tの値をString型に変換する(10000桁以内)
string mpzToString(mpz_t* num){
	char chr[10000]="";
	string str;

	// charの配列に mpz_tの値をいれる
	mpz_get_str(chr, 10, *num);
	str = string(chr);
	return str;
}


// mpz_t型のnumが回文数かどうかを調べる。
bool mpzIsPalindromic(mpz_t* num){
	static string str1, str2;

	str1 = mpzToString(num);
	str2 = str1;
	reverse(str2.begin(), str2.end());
	return str1==str2;
}

/*
bとそれを逆転させたものを足してaにいれる。
a=47 -> 47+74=121
*/
void mpzPalindromicAdd(mpz_t* a, mpz_t* b){
	mpz_t k;
	mpz_init(k);
	mpzFromDigits(&k, deqReverse(mpzIntegerDigits(b)));
	mpz_add(*a, *b, k);
}

// aがLychrel数かどうかを判定する。
bool isLychrel(int a){
	mpz_t tmp;
	mpz_init_set_ui(tmp, a);

	for(int i=0 ; i<50 ; i++){
		mpzPalindromicAdd(&tmp, &tmp);
		if(mpzIsPalindromic(&tmp)) return false;
	}
	return true;
}

int main(){
	int count=0;
	for(int i=1 ; i<10000 ; i++){
		if(isLychrel(i)){
			//cout << i << " is Lychrel number" << endl;
			count++;
		}
		//else cout << i << " is not Lychrel number" << endl;
	}

	cout << count << endl;
}

今までで一番苦労しました・・・
相変わらずmpirにおんぶにだっこなのですが、今回は関数の数が多く、途中で参照渡しが問題になって「うわあああぁぁぁ」状態に。
実は今回はじめてmpirに mpz_get という系列の関数があることを知りました。これでいつでも値を取り出せる！どれだけ僕がマニュアルをちゃんと読んでいないかが浮き彫りになりました。
mpzIntegerDigits の中では引数の値を書き換えてしまっているので、最初にcharの配列に保存し、最後にまた戻すという力技でなんとかしています。