プロジェクトオイラー問145 - sinapusu2002 @ ウィキ

Problem 145 「10億未満に存在するreversibleな数はいくつか?」 †
ある正の整数nについて, [n + reverse(n)]が奇数のみで表されるようなnが存在する. 例えば, 36 + 63 = 99, 409 + 904 = 1313 のように. この性質を持つ数を, reversibleと呼ぶことにする. つまり, 36, 63, 409, 904はrevesibleである. 先頭の0はnでもreverse(n)でも許されない.

1000未満には120個のreversibleな数が存在する.

10億(10＾9)未満では, いくつのreversibleな数が存在するか.

解法
考えやすいので１０桁を例にしてみます。
10桁をa1a2a3a4a5b1b2b3b4b5とすると

 a1a2a3a4a5b1b2b3b4b5
+b5b4b3b2b1a5a4a3a2a1
-----------------------
=A1A2A3A4A5B1B2B3B4B5

となります。
足した結果が１１桁の場合もありますがここでは下記記述により自然に計算されるので深く考える必要がありません。

桁上りがあるとすると矛盾が起きることを証明してみます。
どれかの桁例えばＡ３が繰り上がりＡ4に足されるとします。
すると当然Ｂ３はＡ３と同じ式ですからＢ4は繰り上がります。
Ｂ4とＡ２は同じ式（a2+b4）ですからA2もＡ1によって繰り上がります。
所でＡ１は繰り上がりがないので奇数です。
Ｂ4の結果Ｂ5が繰り上がるとＡ1とＢ5は同じ式です。
Ｂ5はＡ1が奇数なのでＢ5は偶数になり矛盾します。

同様の発想でＡ4Ａ5Ｂ1Ｂ２の範囲も矛盾することがわかります。

つまり偶数桁数のリバース足し算はどの桁も繰り上がりなしとわかります。
よって単純な積で片が付きます。

奇数も同様に考えていくと繰り上がりと繰り上がりなしが一桁ごとに交互に並ぶリバース足し算になり単純な積で片が付きます。

#include<stdio.h>
#include<string.h>
#include<iostream>
__int64 nums[2][2],nums1[2][2],first[2][2];


const int LIMIT=9;

int main(){
	
	memset(nums,0,sizeof(nums));
	memset(first,0,sizeof(first));
	for(int i=0;i<=9;i++){
		for(int j=0;j<=9;j++){
			int n=i+j;
			nums[n%2][n/10]++;
			n++;
			nums1[n%2][n/10]++;
		}
	}
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			int n=i+j;
			first[n%2][n/10]++;
		}
	}
	
	
	__int64 ans=0,n=first[1][0];
	
	for(int i=2;i<=LIMIT;i+=2){
		ans+=n;
		n*=nums[1][0];	
	}
	n=first[1][1]*5;
	__int64 ls[2]={nums1[1][0],nums[1][1]};
	int p=0;
	for(int i=3;i<=LIMIT;i+=4){
		ans+=n;
		for(int j=0;j<2;j++){
			n*=ls[p];
			p=(p+1)%2;
		}
	}
	std::cout<<"ans="<<ans<<"\n";
}