山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.237 作図可能性

問題

No.237 作図可能性 - yukicoder

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

考え方

mathtrain.jp

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

それと、 2^{m} (m \geq 2) 角形も作図可能という点です。

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

コード

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探索を使ったので記事にしました。