回文基数 (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