[Aug6] GCD

qwq

题意

给出n个正整数。有m个询问第l个数到第r个数与g不互质的所有数中,最大的数是多少,并统计区间内最大数的个数。

思路

询问两个数不互质,等同于询问有没有相同的质因数。

对每个质因数建一棵动态开点线段树。

把n个正整数的质因数筛出来加到线段树里。

对每个g把所有质因数筛出来,分别在每棵线段树上查询最大值。

预处理每个数,在std::pair<int,int>数组里,第一关键字里存数值,第二关键字里存编号。

最后查出最大值后用std::upper_bound()std::lower_bound()查就可以知道个数了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <map>
#include <utility>
#define S 32768
char buf[S];int len = 0,pos = 0;
char buf2[S],*p = buf2;
inline char __getchar()
{
if (pos == len)pos = 0,len = fread(buf,1,S,stdin);if(pos == len)return '\0';
return buf[pos++];
}
inline void __putchar(char c) {if(p == buf2 + S)fwrite(buf2,1,S,stdout),p = buf2;*p++ = c;}
inline void flush(){fwrite(buf2,1,p - buf2,stdout);}
inline void putint(int x)
{
if(!x) {__putchar('0');return;}
if(x > 9) putint(x / 10);
__putchar((x % 10) ^ '0');
}
inline int getint()
{
int r = 0,s = 1;char c = __getchar();for(;!isdigit(c);c = __getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = __getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 100010,M = 100000,PRIME_SIZE = 10000,SEG_SIZE = 2000000;
int n,m,a[N];int prime[N],vis[N],pcnt = 0;
inline void seive()
{
memset(vis,0,sizeof(vis));
for(int i = 2;i <= M;i++)
{
if(!vis[i]) prime[++pcnt] = i;
for(int j = 1;j <= pcnt;j++)
{
int x = prime[j];
if(i * x > M) break;
vis[i * x] = 1;
if(!(i % x)) break;
}
}
}
namespace SegmentTree
{
int root[PRIME_SIZE],sz = 0,mx[SEG_SIZE],lc[SEG_SIZE],rc[SEG_SIZE];
inline void insert(int &k,int l,int r,int p,int v)
{
if(!k) k = ++sz;
if(l == r) {mx[k] = v;return;}
int mid = (l + r) >> 1;
if(p <= mid) insert(lc[k],l,mid,p,v);
else insert(rc[k],mid + 1,r,p,v);
mx[k] = std::max(mx[lc[k]],mx[rc[k]]);
}
inline int query(int k,int l,int r,int L,int R)
{
if(!k) return 0;
if(l == L && r == R) return mx[k];
int mid = (l + r) >> 1;
if(R <= mid) return query(lc[k],l,mid,L,R);
if(L > mid) return query(rc[k],mid + 1,r,L,R);
return std::max(query(lc[k],l,mid,L,mid),query(rc[k],mid + 1,r,mid + 1,R));
}
}
std::map<int,int> mp;
std::vector<int> tmp;
std::pair<int,int> info[N];
int dcnt = 0;
int main()
{
seive();
n = getint(),m = getint();
for(int i = 1;i <= n;i++)
{
int x = (a[i] = getint());
info[i] = std::make_pair(a[i],i);
tmp.clear();
for(int j = 1;j <= pcnt && x != 1;j++)
{
if(x % prime[j]) continue;
tmp.push_back(prime[j]);
while(!(x % prime[j])) x /= prime[j];
}
for(int j = 0;j < tmp.size();j++)
{
if(!mp[tmp[j]]) mp[tmp[j]] = ++dcnt;
int &p = SegmentTree::root[mp[tmp[j]]];
SegmentTree::insert(p,1,n,i,a[i]);
}
}
std::sort(info + 1,info + n + 1);
while(m--)
{
int g = getint(),l = getint(),r = getint();
tmp.clear();
for(int j = 1;j <= pcnt && g != 1;j++)
{
if(g % prime[j]) continue;
tmp.push_back(prime[j]);
while(!(g % prime[j])) g /= prime[j];
}
int mx = 0;
for(int j = 0;j < tmp.size();j++)
{
if(!mp[tmp[j]]) continue;
int p = SegmentTree::root[mp[tmp[j]]];
int ret = SegmentTree::query(p,1,n,l,r);
mx = std::max(mx,ret);
}
if(!mx)
{
__putchar('-');
__putchar('1');
__putchar(' ');
__putchar('-');
__putchar('1');
__putchar(10);
}
else
{
std::pair<int,int> Lb = std::make_pair(mx,l),Rb = std::make_pair(mx,r);
int cnt = std::upper_bound(info + 1,info + n + 1,Rb) - std::lower_bound(info + 1,info + n + 1,Lb);
putint(mx);__putchar(' ');putint(cnt);__putchar(10);
}
}
flush();
return 0;
}

(常数有点大,开了fread读优)