Project Euler 303

正の整数 n に対し, f(n) を, n の倍数であり 10 進数で表すと 2 以下の数字のみが用いられる最小の数と定義する.

ゆえに, f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222 である.

また, である.

を求めよ.

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

string numarr[10001];
void insertNumarr(string str, int n);

// str -> f(n)
// 1<= n <= 10000
void insertNumarr(string str, int n){
	for(int i=1 ; n*i <= 10000 ; i++){
		numarr[n*i] = str;
	}	
}

string mpzFind303(int n){
	bool f;
	mpz_t i, k, tmp;

	mpz_init_set_str(i, numarr[n].c_str(), 3);

	if(n==9999) mpz_set_str(i, "11112222222222222222", 3);

	mpz_sub_ui(i, i, 1);

	if(mpz_cmp_si(i,0)<0) mpz_set_ui(i,0);

	mpz_init(k);
	mpz_init(tmp);

	char c[100000];
	
	while(1){
		//i++;
		mpz_add_ui(i,i,1);
		f = true;

		mpz_set(k,i);
		mpz_get_str(c, 3, k);
		mpz_set_str(k, c, 10);
		mpz_mod_ui(tmp, k, n);

		if(mpz_get_ui(tmp)==0){
			char chr[10000]="";
			string str;
			mpz_get_str(chr, 10, k);
			str = string(chr);
			insertNumarr(str, n);

			return str;
		}
	}
}

int main(){
	
	string str;
	char chr[10000];

	numarr[0]="1";
	numarr[1]="1";

	mpz_t sum, f;
	mpz_init_set_ui(sum, 0);
	mpz_init(f);

	for(int i=1 ; i<=10000 ; i++){
		str = mpzFind303(i);
		cout << i << " " << str << endl;

		//charの配列にstringを入れる
		strcpy_s(chr, str.c_str());

		//f = chr;
		mpz_set_str(f, chr, 10);
		mpz_div_ui(f, f, i);

		mpz_add(sum, sum, f);
	}
	
	cout << endl;
	mpz_out_str(stdout, 10, sum);
	cout << endl;
}

@phyllo にそそのかされてすごく後の方の問題をがんばってみた。
紆余曲折あってこの形になりました。f(9999)だけ異常にでかいので手計算。
解説は気が向いたらやります・・・

Project Eulerはforumが見れるんですが、そこに書いてあるコードの速さといったらないです。あとで読んで勉強しないと・・・