COLOCON -Colopl programming contest 2018- C - すぬけそだて――ごはん――

C - すぬけそだて――ごはん――

問題概略

A以上B以下の数から0個以上選ぶ時、それらが互いに素になる組み合わせはいくつか

制約

• $1\le A\le B\le {10}^{18}$
• $B-A\le 35$

解法

高々35個しかないので、偶数の中から0個か1つ選び、奇数の中から選ぶ数を全探索できる(18 * 2^17 程度 )

選んだ組み合わせが互いに素か判別するために、bitで素因数をもたせる。

選んだものの素因bitを足していき、かつ毎回重複するものがないかを調べればbit桁数程度で終わる

よって、O(18 * 2^17 * 10 )ぐらい

問題の芯

bitは複数の条件で、かぶりがあるかないかO(1)で求められる

public static void main(String[] args)
    {
        A = sc.nextLong();
        B = sc.nextLong();
        N = (int) (B - A + 1);
        //選ばない時用に一つ増やす
        long[] evens = new long[A % 2 == 0 && N % 2 == 1 ? N / 2 + 1 : N / 2];
        long[] odds = new long[N - evens.length];
        for (int i = 0, e = 0, o = 0; i < N; i++)
        {
            if ((A + i) % 2 == 0) evens[e++] = A + i;
            else odds[o++] = A + i;
        }
        //何を因数にもつかbitに持たせる
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        long[] ebits = new long[evens.length+1] ;
        long[] obits = new long[odds.length];

        ebits[0] = 0;//2の倍数を選ばない場合
        for (int i = 0; i < evens.length; i++)
        {
            for (int p = 0; p < prime.length; p++)
            {
                if (evens[i] % prime[p] == 0)
                {
                    ebits[i+1] |= 1 << p;
                }
            }
        }
        for (int i = 0; i < odds.length; i++)
        {
            for (int p = 0; p < prime.length; p++)
            {
                if (odds[i] % prime[p] == 0)
                {
                    obits[i] |= 1 << p;
                }
            }
        }
        //2の倍数に対して奇数全探索
        //2の倍数を使わない場合も必要
        long cou = 0;
        for (long ebit : ebits)
        {
            for (int omask = 0; omask < (1 << odds.length); omask++)
            {
                long factors = ebit;//互いに素か判定するため足していく
                boolean isJoint = true;
                //その組み合わせが可能か
                for (int i = 0; i < odds.length; i++)
                {
                    if (((omask >> i) & 1) == 0) continue;
                    //共通の素因数がない場合
                    if ((factors & obits[i]) == 0)
                    {
                        factors |= obits[i];
                    }
                    else
                    {
                        isJoint = false;
                        break;
                    }
                }
                if (isJoint) cou++;
            }
        }
        System.out.println(cou);
    }