Project Euler 43

数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分語が面白い性質を持っている.

を1桁目, を2桁目の数とし, 以下順にを定義する. この記法を用いると次のことが分かる.

=406は2で割り切れる
=063は3で割り切れる
=635は5で割り切れる
=357は7で割り切れる
=572は11で割り切れる
=728は13で割り切れる
=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2043

#include <iostream>
#include <deque>
using namespace std;

const int NUMSIZE = 10;
bool num[NUMSIZE];

// num初期化
void numInit(){
	for(int i=0 ; i<NUMSIZE ; i++){
		num[i] = true;
	}
}

// nの階乗を返す
long long factorial(int n){
	if(n==0 || n==1) return 1;

	long long k=1;
	for(int i=2 ; i<=n ; i++){
		k*=i;
	}
	return k;
}

// num中でn番目のtrueの位置を返す
int trueAt(int n){
	int pos=0, tgt=0;
	while(1){
		if(num[pos]){
			if(n==tgt) break;
			tgt++;
		}
		if(n==tgt-1) break;
		pos++;
	}

	return pos;
}


// dig桁の、n番目の順列の数を返す。
// 不完全。dig=10だと 1<2<3<4<5<6<7<8<9<0の順になっている。
long long PermutationAt(int dig, int n){
	numInit();
	long long ans=0;

	for(int j=dig-1 ; j>=0 ; j--){
		ans *=10;
		int k = (int)(((n-1)%factorial(j+1))/factorial(j));
		int p = trueAt(k);
		//cout << p;
		ans += (p+1)%10;
		num[p] = false;
	}
	return ans;
}

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

int fromDigits(deque<int> arr){
	int x=0;
	while(!arr.empty()){
		x *= 10;
		x += arr[0];
		arr.pop_front();
	}
	return x;
}


// nから3桁取り出す
int take3dig(long long n, int a){
	deque<int> ndeq = integerDigits(n);
	int dig = ndeq.size();

	for(int i=1 ; i<a ; i++) ndeq.pop_front();
	for(int i=0 ; i<=dig-3-a ; i++) ndeq.pop_back();

	return fromDigits(ndeq);
}


int main(){
	long long k = factorial(10) - factorial(9);

	long long n, ans=0;
	for(long long i=1 ; i<k ; i++){
		n = PermutationAt(10, i);

		if(take3dig(n,8)%17==0 &&
			take3dig(n,7)%13==0 &&
			take3dig(n,6)%11==0 &&
			take3dig(n,5)%7==0 &&
			take3dig(n,4)%5==0 &&
			take3dig(n,3)%3==0 &&
			take3dig(n,2)%2==0 ){
				cout << n << endl;
				ans += n;
		}

	}
	cout << endl << ans << endl;
}

これは面倒だった！permutationがらみの関数がとっても適当。