Ant colony
题目链接
分类：data structures number theory
1.题意概述
给你一个数列
a[1..n]
，给定一个区间
[l,r]
，求区间内的某个数
x
可以整除区间内所有值，求此
x的个数，显然个数就是区间内所有数的
gcd(al，al+1,al+2,...,ar−1,ar)
相同个数。
2.解题思路
因为是查询区间的gcd，可以考虑用线段树
O(logN)
解决，求任何区间内某个数的个数可以先用pair记录gcd值和统计的个数，再排序用二分确定上下界。
3.AC代码
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define e exp(1.0)
#define pi acos(-1.0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
#define INF 0x3f3f3f3f
#define maxn 100111
#define N 1111
typedef vector<int> VI;
typedef pair<
int,
int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int mod =
1e9 +
7;
int a[maxn];
class SegmentTree {
public:
#define lson root << 1
#define rson root << 1 | 1
#define lent (t[root].r - t[root].l + 1)
#define lenl (t[lson].r - t[lson].l + 1)
#define lenr (t[rson].r - t[rson].l + 1)
struct Tree {
int l, r;
PII val;
} t[maxn <<
4];
void pushup(
int root) {
if (t[lson].val.fi == t[rson].val.fi) {
t[root].val = mp(t[lson].val.fi, t[lson].val.se + t[rson].val.se);
return;
}
int cur = __gcd(t[lson].val.fi, t[rson].val.fi);
if (cur == t[lson].val.fi) {
t[root].val = t[lson].val;
}
else if (cur == t[rson].val.fi) {
t[root].val = t[rson].val;
}
else {
t[root].val = mp(cur,
0);
}
}
void build(
int l,
int r,
int root) {
t[root].l = l;
t[root].r = r;
if (l == r) {
t[root].val = mp(a[l],
1);
return;
}
int mid = l + r >>
1;
build(l, mid, lson);
build(mid +
1, r, rson);
pushup(root);
}
PII query(
int l,
int r,
int root) {
if (r < t[root].l || l > t[root].r)
return mp(
0,
0);
if (l <= t[root].l && t[root].r <= r)
return t[root].val;
int mid = t[root].l + t[root].r >>
1;
PII a = query(l, r, lson);
PII b = query(l, r, rson);
if (a.fi == b.fi)
return mp(a.fi, a.se + b.se);
int cur = __gcd(a.fi, b.fi);
if (cur == a.fi)
return a;
if (cur == b.fi)
return b;
return mp(cur,
0);
}
#undef lenr
#undef lenl
#undef lent
#undef rson
#undef lson
} T;
int main() {
#ifndef ONLINE_JUDGE
freopen(
"in.txt",
"r", stdin);
freopen(
"out.txt",
"w", stdout);
long _begin_time = clock();
#endif
int n, k;
scanf(
"%d", &n);
rep(i,
1, n +
1)
scanf(
"%d", &a[i]);
T.build(
1, n,
1);
scanf(
"%d", &k);
while (k--) {
int l, r;
scanf(
"%d%d", &l, &r);
PII ans = T.query(l, r,
1);
printf(
"%d\n", r - l +
1 - ans.se);
}
#ifndef ONLINE_JUDGE
long _end_time = clock();
printf(
"time = %ld ms.", _end_time - _begin_time);
#endif
return 0;
}
