题意:求区间内与其他任何数都互质的数的个数。
题解:求出每个数左右互质的边界。然后对询问排序,通过树状数组求解。
讲道理真的好难啊= =
http://blog.csdn.net/dyx404514/article/details/15507209 这个博客讲的最清楚(竟然是戴神的博客=。= 听过戴神讲splay,现在还不会……
#include <bits/stdc++.h> using namespace std; const int N = ; /***素数打表***/
int p[N];
int is_p[N+];
int cnt_p;
void get_p() {
for (int i = ; i <= N; ++i) is_p[i] = ;
cnt_p = is_p[] = is_p[] = ;
for (int i = ; i <= N; ++i) {
if (is_p[i]) {
p[cnt_p++] = i;
for (int j = i * ; j <= N; j += i) is_p[j] = ;
}
}
}
/***因数分解***/
int fac[N]; // 记录出现的因数
int cal_fac(int x) {
int tmp = x;
int idx = ;
int i;
for (i = ; p[i] <= tmp/p[i]; ++i) {
if (tmp%p[i]) continue;
while (tmp%p[i] == ) tmp /= p[i];
fac[idx++] = p[i];
}
if (tmp != ) fac[idx++] = tmp;
return idx;
}
/***计算每个数互质的最左最右区间***/
int l[N], r[N];
int adj[N];
int a[N];
void cal_inv(int n) {
for (int i = ; i < N; ++i) adj[i] = ;
for (int i = ; i <= n; ++i) {
int cnt = cal_fac(a[i]);
l[i] = ;
for (int j = ; j < cnt; ++j) {
l[i] = max(l[i], adj[fac[j]]);
adj[fac[j]] = i;
}
}
for (int i = ; i < N; ++i) adj[i] = n+;
for (int i = n; i >= ; --i) {
r[i] = n+;
int cnt = cal_fac(a[i]);
for (int j = ; j < cnt; ++j) {
r[i] = min(r[i], adj[fac[j]]);
adj[fac[j]] = i;
}
}
} struct node {
int l, r, id;
bool operator<(const node x) const { return l < x.l; }
} qry[N]; int bit[N];
int lowbit(int x) { return x&-x; }
void add(int x, int v, int n) { while(x<=n) bit[x]+=v,x+=lowbit(x); }
int sum(int x) { int ans=; while(x) ans+=bit[x],x-=lowbit(x); return ans; } vector<int> lb[N]; // lb[i] 以i为左边界的数
int ans[N];
int main() {
//freopen("in.txt", "r", stdin);
get_p();
int n, k;
while (~scanf("%d%d", &n, &k)) {
if (n == ) break;
for (int i = ; i <= n; ++i) {
scanf("%d", a+i);
}
cal_inv(n); for (int i = ; i < k; ++i) {
scanf("%d%d", &qry[i].l, &qry[i].r);
qry[i].id = i;
}
sort(qry, qry+k);
for (int i = ; i <= n; ++i) lb[i].clear();
memset(bit, , sizeof bit);
for (int i = ; i <= n; ++i) {
if (!l[i]) { add(i, , n); add(r[i], -, n); }
else lb[l[i]].push_back(i);
}
int pos = ;
for (int i = ; i < k; ++i) {
while (qry[i].l > pos) {
add(pos, -, n);
add(r[pos], , n);
for (unsigned j = ; j < lb[pos].size(); ++j) {
int x = lb[pos][j];
add(x, , n);
add(r[x], -, n);
}
pos++;
}
ans[qry[i].id] = sum(qry[i].r)-sum(qry[i].l-);
}
for (int i = ; i < k; ++i) {
printf("%d\n", ans[i]);
}
} return ;
}