ぐるぐる数

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);
	}
}