yukicoder No.237 作図可能性

問題はこちら
No.237 作図可能性 - yukicoder

問題文からリンクされている定規とコンパスによる作図 - Wikipediaによれば、n≧3に対し、正n角形が作図可能であることの必要十分条件は
nが0個以上の相異なるフェルマー素数と2ベキ（1含む）の積で表されていること
フェルマー数 - Wikipediaによれば、10^9以下のフェルマー素数は3,5,17,257,65537の5つ
（そもそもこの5つ以外には存在も非存在も示されていない）

ということで、これらの積で書ける数のうち、Aより小さいものがいくつあるか数える

int main(){
	long m,x[]={3,5,17,257,65537};
	int i,j,a,s=0;
	scanf("%d",&a);
	for(i=0;i<30;i++)for(j=0;j<32;j++){
		m=1<<i;
		if(j&1)m*=x[0];
		if(j&2)m*=x[1];
		if(j&4)m*=x[2];
		if(j&8)m*=x[3];
		if(j&16)m*=x[4];
		if(m>2&&m<=a)s++;
	}
	printf("%d",s);
	return 0;
}

とりあえずこの方針で短くしてみようか
x[i]の値は2^(2^k)+1なので(1<<(1<<k))+1で求めることができる

i,j,k,a,s;
main(long m){
	for(scanf("%d",&a);i<30;i++)for(j=0;++j<33;s+=m<=a)for(m=1<<i,k=0;k<5;k++)m*=j>>k&1?(1<<(1<<k))+1:1;
	s=!printf("%d",s-2);
	//mが1,2の時も加算されているので2を引く
}

ぐっと睨んで

i,j,k,a,s;
main(long m){
	for(scanf("%d",&a);i<30;i++)for(j=0;++j<33;s+=m<=a)for(m=1<<i,k=1;k<32;k*=2)m+=j&k?m<<k:0;
	s=!printf("%d",s-2);
}

これで134B

方針を変える
・問題0(A)：1以上A以下の数のうち2の累乗数の個数を考える
（※「問題0(A)」のAは問題文中のAと対応している）
A<1なら0個、そうでなければfloor(log2(A))+1個存在する
・問題1(A)：1以上A以下の数のうち2の累乗数と高々1つの3の積で表せる数の個数を考える
3を使わないときは問題0(A)
3を使うときは問題0(A/3)
・問題2(A)：1以上A以下の数のうち2の累乗数と高々1つの3と高々1つの5の積で表せる数の個数を考える
5を使わないときは問題1(A)
5を使うときは問題1(A/5)
……
とこんな感じで再帰的に解くことができるので問題b(A)の答えを返す関数f(A,b)を次のように作れる

f(a,b){
	if(b==0)return a?log2(a)+1:0;
	else return f(a,b-1)+f(a/((1<<(1<<b-1))+1),b-1);
}

ということでこれにより

n;
f(a,b){return b--?f(a,b)+f(a/((1<<(1<<b))+1),b):a?log2(a)+1:0;}
main(){n=!printf("%d",f(atoi(gets(&n)),5)-2);}

111B

2016/10/20追記
fに改良の余地がある

a/((1<<(1<<b))+1)
a/=(1<<(1<<b))+1

a?log2(a)+1:0
log2(a+.4)+1
//a>0なら1未満の数を加えても影響ないので、a==0のときに0になるように調整

これらを合わせて2B短縮の109B