HDU - 6287 口算训练 （质因子分解 + 二分）

题意：给一个序列，问 [l, r] 连续区间的乘积能否被 d 整除

思路：用 vector 记录每个质因子在序列中出现的位置，upper_bound(vec[p].begin(), vec[p].end, r) - lower_bound(vec[p].begin(), vec[p].end(), l) 即为质数 p 在区间 [l, r] 中出现的次数。（可以不筛素数，直接试除

大数模板和Java都会超时

#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const db eps = 1e-6;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int t, n, m, l, r, d, a[N], pri[N], tot;
vectorvec[N];
bool vis[N];

void init() {
    tot = 0;
    vis[0] = vis[1] = 1;
    for(int i = 2; i < N; ++i) {
        if(!vis[i]) {
            pri[++tot] = i;
            for(int j = i + i; j < N; j += i) vis[j] = 1;
        }
    }
}

void solve(int x, int id) {
    int tmp = x;
    for(int i = 1; pri[i] * pri[i] <= tmp && i <= tot; ++i) {
        while(x % pri[i] == 0) {
            x /= pri[i];
            vec[pri[i]].emplace_back(id);
        }
    }
    if(x > 1) vec[x].emplace_back(id);
}

bool check(int l, int r, int p, int cnt) {
    int ans = upper_bound(vec[p].begin(), vec[p].end(), r) - lower_bound(vec[p].begin(), vec[p].end(), l);
    return ans >= cnt;
}

int main() {
    init();
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i < N; ++i) vec[i].clear();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            solve(a[i], i);
        }
        while(m--) {
            scanf("%d%d%d", &l, &r, &d);
            int dd = d;
            bool flag = 1;
            for(int i = 1; pri[i] * pri[i] <= dd && i <= tot; ++i) {
                if(d % pri[i] == 0) {
                    int cnt = 0;
                    while(d % pri[i] == 0) {
                        d /= pri[i];
                        ++cnt;
                    }
                    if(!check(l, r, pri[i], cnt)) {
                        flag = 0;
                        break;
                    }
                }
            }
            if(flag && d > 1 && !check(l, r, d, 1)) flag = 0;
            if(flag) printf("Yesn");
            else printf("Non");
        }
    }
    return 0;
}