D - LCM Rush AtCoder Beginner Contest 020

D - LCM Rush
問題概略
1~Nについて、lcm(i,K)を足し合わせた余りを求めよ。

解法
約数は高々1400個しか無いのでgcd(i,k)の値で複数の物を纏められる。
gcd(a,b)=1の時、lcm(a,b) = a * b / gcd(a,b) より　bと互いに素であるiの合計 * b / となり、iの合計は包除原理を用いて解ける。
gcd(a,b)がcの際はgcd(a/c,b/c)で同様に求められる。

 public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        K = ni();
        setPrimes();
        ArrayList<Integer> div = new ArrayList<>();
        for (int i = 1; i * i <= K; i++) {
            if (K % i == 0) {
                div.add(i);
                if (i * i != K) div.add(K / i);
            }
        }
        long res = 0;
        for (Integer gcd : div) {
            //                            sum ( N / gcd , K / gcd) * gcd / gcd * K
            long par = modMul(lcmRush(N / gcd, K / gcd), K);
            res = modSum(res, par);
        }
        System.out.println(res);
    }

    static ArrayList<Integer> factorization(int n) {
        if (primes == null) setPrimes();
        ArrayList<Integer> fact = new ArrayList<>();
        for (int p : primes) {
            if (n % p == 0) fact.add(p);
            while (n % p == 0) n /= p;
            if (n == 1) break;
        }
        if (n != 1) fact.add(n);
        return fact;
    }

    public static long lcmRush(int n, int k) {
        ArrayList<Integer> fact = factorization(k);
        int fsize = fact.size();
        long sum = 0;
        //包除原理
        for (int m = 0; m < (1 << fsize); m++) {
            long va = 1;
            for (int i = 0; i < fsize; i++) {
                if (bitGet(m, i)) va *= fact.get(i);
            }
            long s = va;
            long t = n / va * va;
            long kosu = n / va;
            // long part = modMul(s + t) * kosu / 2;
            long part = modDiv(modMul(modSum(s, t), kosu), 2);
            if (Integer.bitCount(m) % 2 == 1) sum = modDiff(sum, part);
            else sum = modSum(sum, part);
        }
        return sum;
    }