[yukicoder] No.237 作図可能性

問題

No.237 作図可能性 - yukicoder

コンパスと定規を使って正 角形を作図できるかという問題です。

考え方

mathtrain.jp

定理を用いて作図可能な整数を求めます。ここで注意しなければならない点は、制約の下でフェルマー素数が高々 つしかないということです。

それと、 角形も作図可能という点です。

したがって、bit探索を用いて任意のフェルマー素数の積の配列を用意し、 と掛けた値が作図可能な整数となります。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Exec0237 {
    static long []b;
    static long[]F = {3, 5, 17, 257, 65537};
    static int cnt = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        scan.close();

        long []a = new long[30];
        for(int i = 0; i < 30; i++) {
            a[i] = (long)Math.pow(2, i);
        }
        b = new long[32];


        int[] bit = new int[5];
        rec(0, 5, bit);
        Arrays.sort(b);

        int ans = 0;
        for(int i = 0; i < 30; i++) {
            for(int j = 0; j < 32; j++) {
                long t = a[i] * b[j];
                if(3 <= t &&t <= A) {
                    ans++;
                }
            }
        }
        System.out.println(ans);

    }
    static void rec(int k, int n, int[] S) {
        if(k == n) {
            long t = calc(S);
            b[cnt] = t;
            cnt ++;
            return;
        }
        rec(k + 1, n, S);
        S[k] = 1;
        rec(k + 1,n, S);
        S[k] = 0;
    }
    static long calc(int[] S) {
        long t = 1;
        for(int i = 0; i < S.length; i++) {
            if(S[i] == 1) {
                t *= F[i];
            }
        }
        return t;
    }
}

感想

定理を知っていないと多分解けない問題だと思いますが、bit探索を使ったので記事にしました。