回文基数 (O(√n))

問題:
http://qiita.com/Nabetani/items/dabe8ec57e0313229552
http://nabetani.sakura.ne.jp/hena/ord17scheherazade/

http://qiita.com/shiracamus/items/20ae065c90007279c753 のアイデアをお借りしました。
O(√n)です。
「あるN(Nは単数でない自然数(2以上の整数))をn進法(nは単数でない自然数)で表すとする。それが2桁以上の回文となるならば、nはsqrt(N-1)以下か、N-1を整数除算した商である」という定理が導かれますが、証明はできません(汗)
Mi_Sawa氏よりコメントを頂きました。

nが大体sqrt(N)以上くらいならまぁn進2桁なのでan+a=Nなるaが各桁になっている訳で, N=a(n+1)になるからNの約数-1を全部考えればいいよねという感じかな.

ありがとうございました。

• n<=sqrt(N-1)の場合は全部調べる
• (sqrt(N)を越える最小の整数)<=n<=N-1の場合、N=an+a=a(n+1)<=>n=N/a-1とできるので、 Nの約数aを列挙し1を引けば良い
• と思ったのですが、2=6/2-1を捕捉してしまう問題が出たので今回はこちらもpalindrome判定します--;

Language	Validator C++(Text)	Validator Ruby(HTTP)
C++	0.02s	0.22s
Ruby	0.06s	0.26s

0.2秒は鍋谷さんのサーバーからHTMLを拾って解析する時間です。
おそらく0.02sはfork/execlに要する時間と見て良いと思われます。

clang -O2 hena17pre.c;echo 999999999|time ./a.out # 4.83s
clang++ -O2 hena17pre_fast.cpp;echo 999999999|time ./a.out # 0.00s

hena17pre_fast.cpp

//http://qiita.com/Nabetani/items/dabe8ec57e0313229552
//http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
# include <deque>
# include <cstdio>
# include <cmath>
bool palindrome(int n,int b){
	int n0=n,n1=0;
	for(;n0;n0/=b)n1=n1*b+n0%b;
	return n1==n;
}
int main(){
	int n,i;
	for(;~scanf("%d",&n);){
		if(n<3)puts("-");
		else{
			std::deque<int> result;
			for(i=sqrt(n-1);i>1;i--){
				if(palindrome(n,(n-1)/i))result.push_back((n-1)/i);
				if((n-1)/i!=i&&palindrome(n,i))result.push_front(i); // n-1 might be a square number
			}
			for(i=0;i<result.size();i++)printf("%d,",result[i]);
			printf("%d\n",n-1);
		}
		fflush(stdout);
	}
}

hena17pre_fast.rb

# !/usr/bin/env ruby
# http://qiita.com/Nabetani/items/dabe8ec57e0313229552
# http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
STDOUT.sync=true
class Integer
	def palindrome?(b)
		n0=self
		n1=0
		while n0>0
			n1=n1*b+n0%b
			n0/=b
		end
		n1==self
	end
end
while gets
	n=$_.to_i
	if n<3 then puts '-';next end
	result=[]
	Math.sqrt(n-1).to_i.downto(2).each{|i|
		result.push((n-1)/i) if n.palindrome?((n-1)/i)
		result.unshift(i) if (n-1)/i!=i&&n.palindrome?(i) # n-1 might be a square number
	}
	puts (result+[n-1])*','
end