Ruby
どう書く
yhpg
C言語
crystal

O(N)です.昔はO(logN)にできるようちゃんと解析していたのですが申し訳ないです.crystal build --releaseで2分でした.ruby --jitはCase63あたりで力尽きました.

#!/usr/bin/ruby

#http://nabetani.sakura.ne.jp/hena/orde31rotnum/
#https://qiita.com/Nabetani/items/d139d5ef70aa23c2d038

# can run on both Ruby and Crystal.

def chk(n,b)
n,r=n.divmod b
while n>0
n,r0=n.divmod b
if r0!=r && (r0+1)%b!=r
return false
end
r=r0
end
true
end

while s=gets
b_,x_,y_=s.chomp.split(",")
b=b_.to_i
x=x_.to_i(b)
y=y_.to_i(b)
p (x..y).count{|i|chk(i,b)}
STDOUT.flush
end

gcc-8 -fopenmp -O3では30秒で実行できました.

[追記] 30秒なのはこのMacBookの物理コア数が2コアだからです.大学のスパコンでは3秒でした.

//http://nabetani.sakura.ne.jp/hena/orde31rotnum/

//https://qiita.com/Nabetani/items/d139d5ef70aa23c2d038

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool get(int *b,int *x,int *y){
char s[999];
if(!fgets(s,999,stdin))return false;
*b=strtol(strtok(s,","),NULL,10);
*x=strtol(strtok(NULL,","),NULL,*b);
*y=strtol(strtok(NULL,","),NULL,*b);
return true;
}

bool chk(int n,int b){
div_t x,y;
x=div(n,b);
for(;x.quot;){
y=div(x.quot,b);
if(y.rem!=x.rem && (y.rem+1)%b!=x.rem)return false;
x=y;
}
return true;
}

int main(){
int b,x,y;
for(;get(&b,&x,&y);){
if(b==2){
printf("%d\n",y-x+1);
}else{
int r=0;
#pragma omp parallel for reduction(+:r)
for(int i=x;i<=y;i++){
r+=chk(i,b);
}
printf("%d\n",r);
}
fflush(stdout);
}
}

std::futureを使った並列化は以下のようになります。ちゃんとnum_threads分の並列化をするようにしないと重くなってしまいます。

//http://nabetani.sakura.ne.jp/hena/orde31rotnum/

//https://qiita.com/Nabetani/items/d139d5ef70aa23c2d038

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include <vector>
#include <future>

bool get(int *b,int *x,int *y){
char s[999];
if(!fgets(s,999,stdin))return false;
*b=strtol(strtok(s,","),NULL,10);
*x=strtol(strtok(NULL,","),NULL,*b);
*y=strtol(strtok(NULL,","),NULL,*b);
return true;
}

bool chk(int n,int b){
div_t x,y;
x=div(n,b);
for(;x.quot;){
y=div(x.quot,b);
if(y.rem!=x.rem && (y.rem+1)%b!=x.rem)return false;
x=y;
}
return true;
}

int main(){
int b,x,y;
for(;get(&b,&x,&y);){
if(b==2){
printf("%d\n",y-x+1);
}else{
int num_threads=std::thread::hardware_concurrency();
auto f=[&](int start)->int{
int r=0;
for(int j=x+start;j<=y;j+=num_threads){
r+=chk(j,b);
}
return r;
};
std::vector<std::future<int>>task;
for(int i=1;i<num_threads;i++)task.push_back(std::async(std::launch::async,f,i));
int r=f(0);
for(auto &t:task)r+=t.get();
printf("%d\n",r);
}
fflush(stdout);
}
}