[BZOJ5358][Lydsy1805月賽]口算訓練（質因數分解+離線亂搞）

亂搞？？？？？又是？？？？？

Address

https://begin.lydsy.com/JudgeOnline/upload/201805.pdf

Solution

發現好多人用主席樹

這裡講一種跑得更快的離線做法。

首先，對于每個詢問 (l,r,d) ( l , r , d ) ，可以将 d d 分解質因數。

如果分解的結果是 d=∏ri=1pqiid=∏i=1rpiqi ，并且質因子 x x 在 [l,r][l,r] 内所有數中出現的次數之和為 sum[l,r,x] s u m [ l , r , x ] ，那麼詢問轉化為，判斷是否滿足：

∀1≤i≤r,sum[l,r,pi]≥qi ∀ 1 ≤ i ≤ r , s u m [ l , r , p i ] ≥ q i

嘗試把每個數進行質因數分解（由于有多組資料，是以可以預處理出 [1,105] [ 1 , 10 5 ] 内所有數的質因數分解以提高效率，而一個 [1,105] [ 1 , 10 5 ] 的質因子個數不超過 6 6 ）

把詢問 sum[l,r,x]sum[l,r,x] 拆成 sum[1,l−1,x] s u m [ 1 , l − 1 , x ] 和 sum[1,r,x] s u m [ 1 , r , x ] 。

于是詢問再次轉化：求一個字首内，質因子 x x 的出現次數。

但可以發現，如果對于每個質因子都維護一個字首和，那麼空間是 O(n2)O(n2) 的，開不下。

于是将詢問離線，按照字首的長度（末尾标号）從小到大排序。

用一個指針 i i 将序列從左到右掃描一遍，掃描的過程中，維護字首 [1,i][1,i] 内各個因子的出現次數。這樣，當 i=k i = k 的時候，就能立即回答形如 sum[k,x] s u m [ k , x ] 的詢問。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N =  + , M = N << , E = ;
int n, m, w, a[N], tot, pri[N], pr[N], num[N][E], pw[N][E], qn[N], cnt[N],
ans[N][E]; bool mark[N]; struct cyx {int i, id;} q[M];
inline bool comp(const cyx &a, const cyx &b) {return a.i < b.i;}
void sieve() {
    int i, j; mark[] = mark[] = ; For (i, , ) {
        if (!mark[i]) pri[++tot] = i; For (j, , tot) {
            if (l * i * pri[j] > ) break; mark[i * pri[j]] = ;
            if (i % pri[j] == ) break;
        }
    }
    For (i, , ) {
        int x = i; For (j, , tot) {
            int y = pri[j]; if (l * y * y > i) break;
            if (x % y) continue; num[i][++pr[i]] = y;
            while (x % y == ) pw[i][pr[i]]++, x /= y;
        }
        if (x > ) num[i][++pr[i]] = x, pw[i][pr[i]] = ;
    }
}
void work() {
    int i, j, l, r; n = read(); m = read(); For (i, , n) a[i] = read(); w = ;
    For (i, , m) {
        For (j, , ) ans[i][j] = ; l = read(); r = read(); qn[i] = read();
        q[++w] = (cyx) {l - , w - }; q[++w] = (cyx) {r, w - };
    }
    sort(q + , q + w + , comp); memset(cnt, , sizeof(cnt)); l = ;
    For (i, , n) {
        if (i) For (j, , pr[a[i]]) cnt[num[a[i]][j]] += pw[a[i]][j];
        while (l <= w && q[l].i == i) {
            int id = (q[l].id >> ) + ; For (j, , pr[qn[id]])
                if (q[l].id & ) ans[id][j] += cnt[num[qn[id]][j]];
                else ans[id][j] -= cnt[num[qn[id]][j]]; l++;
        }
    }
    For (i, , m) {
        double res = ; For (j, , pr[qn[i]])
            res = res && ans[i][j] >= pw[qn[i]][j]; puts(res ? "Yes" : "No");
    }
}
int main() {
    int T = read(); sieve(); while (T--) work(); return ;
}