Minions and Voting [CodeChef March Challenge 2018 Div1 E]

https://www.codechef.com/MARCH18A/problems/GCDCNT

N要素の配列Aがある。
これにQ個の2種類のクエリを処理する。
「1 X Y」 : A[X]をYにする
「2 L R G」 : L≦i≦Rの中でgcd(G, A[i])=1となる要素数を返す

前提知識

• 平方分割
• 包除原理

解法

https://www.codechef.com/viewsolution/17610281

平方分割しよう。
各バケットに用意するのは、「cnt[s][i] := s番目のバケット内のiの倍数の数」である。
処理に移る前に配列edも事前計算しておく。
「ed[i] := iを素因数分解した時に使われる素因数の集合」
配列の各要素で、対応するバケットに自分の約数をカウントさせておくが、素因数分解した時に各素因数の指数部が1となるように変えた数の約数だけカウントしておく。
こうすることで包除原理がやりやすくなる。
　
クエリ1の場合は、対応するバケットの約数を減らして消したあと、変更後の数で対応するバケットの約数を増やす。
　
クエリ2の場合は、半端なバケットではgcdを取って=1となる物を数え上げる。
バケット毎では包除原理で互いに素な個数を数え上げる。
例えばX=30であれば、「(1の倍数) - (2の倍数) - (3の倍数) - (5の倍数) + (6の倍数) + (10の倍数) + (15の倍数) - (30の倍数)」で互いに素な個数が求まる。
2*3*5*7*11*13*17が5*10^5くらいなので、この時使われる素因数は最大7個。
よって、この包除原理はO(2^7)が最大である。
　
これでO(Q*sqrt(N)*2^7)で間に合う。

int N, A[50101], Q;
vector<int> ed[101010];
const int S = 250;
int cnt[250][101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 1, 101010) {
        auto ep = enumpr(i);
        fore(p, ep) ed[i].push_back(p.first);
    }
 
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cin >> Q;
    rep(i, 0, N) {
        int n = ed[A[i]].size();
        rep(msk, 0, 1 << n) {
            int p = 1;
            rep(j, 0, n) if (msk & (1 << j)) p *= ed[A[i]][j];
            cnt[i / S][p]++;
        }
    }
 
    rep(q, 0, Q) {
        int T; cin >> T;
        if (T == 1) {
            int i, x; cin >> i >> x; i--;
 
            int n = ed[A[i]].size();
            rep(msk, 0, 1 << n) {
                int p = 1;
                rep(j, 0, n) if (msk & (1 << j)) p *= ed[A[i]][j];
                cnt[i / S][p]--;
            }
 
            A[i] = x;
 
            n = ed[A[i]].size();
            rep(msk, 0, 1 << n) {
                int p = 1;
                rep(j, 0, n) if (msk & (1 << j)) p *= ed[A[i]][j];
                cnt[i / S][p]++;
            }
        } else {
            int l, r, x; cin >> l >> r >> x;
            l--; r--;
 
            int ans = 0;
            while (l <= r && l % S) {
                if (gcd(A[l],x) == 1) ans++;
                l++;
            }
            while (r >= l && r % S != S - 1) {
                if (gcd(A[r],x) == 1) ans++;
                r--;
            }
            while (l < r) {
                int n = ed[x].size();
                rep(msk, 0, 1 << n) {
                    int p = 1, c = 0;
                    rep(i, 0, n) if (msk & (1 << i)) p *= ed[x][i], c++;
                    
                    if (c % 2) ans -= cnt[l / S][p];
                    else ans += cnt[l / S][p];
                }
                l += S;
            }
 
            printf("%d\n", ans);
        }
    }
}