HDU5812 Distance
数论
题解
OI
题意
给出一个空集合和三个操作。操作I向集合中插入元素X，操作D删除集合中的元素X，操作Q，查询集合中的所有元素与X的最小距离是多少？
定义最小距离为从x变为y只通过乘或者除素数所需要的最少操作次数。例如：，因为
分析
定义表示x的质因数个数，易知
由于，所以可以预处理出pfac。
对于每次查询，可以暴力枚举x的因数作为两数的GCD，()，然后再枚举这个GCD的倍数作为另外一个数，判断这个数在集合里面是否存在，再更新ans。
但是这样跑不过。考虑到不会超过20，聪明一些的做法是开一个数组cnt[i][j]，表示当前集合中满足含有因数i，同时含有的除了i后质因数数量是j的数的数目，就可以在插入和删除时维护cnt数组，查询时对于x的每一个因数枚举j就完了。总时间复杂度
代码
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;
const int MAXN = 200010;
const int MAXA = 1000010;
const int AMXA = 1000000;
const int INF = 0x3f3f3f3f;
int prime[MAXA];
int prime_cnt;
bool isntp[MAXA];
int pcnt[MAXA];
void count_factor() {
pcnt[1] = 0;
for(int i = 2;i<=AMXA;i++){
if(!isntp[i]){
prime[++prime_cnt] = i;
pcnt[i] = 1;
}
for(int j = 1;j<=prime_cnt && i*prime[j] <= AMXA;j++){
isntp[i*prime[j]] = true;
pcnt[i*prime[j]] = pcnt[i] + 1;
if(i % prime[j] == 0){
break;
}
}
}
}
set<int> s;
int c[MAXA][20];
void add(int x){
for(int i = 1;i*i <= x;i++){
if(x % i == 0){
c[i][pcnt[x/i]]++;
if(i*i != x){
c[x/i][pcnt[i]]++;
}
}
}
}
void del(int x){
for(int i = 1;i*i <= x;i++){
if(x % i == 0){
c[i][pcnt[x/i]]--;
if(i*i != x){
c[x/i][pcnt[i]]--;
}
}
}
}
int main(){
count_factor();
int q;
int T = 0;
while((cin >> q) && q > 0){
cout << "Case #" << ++T << ":" << endl;
s.clear();
memset(c,0,sizeof c);
for(int i = 1;i<=q;i++){
char opr[5];
int x;
scanf("%s%d",opr,&x);
switch(opr[0]){
case 'I':
if(s.count(x) == 0){
s.insert(x);
add(x);
}
break;
case 'D':
if(s.count(x) > 0){
s.erase(x);
del(x);
}
break;
case 'Q':
if(s.size() == 0){
cout << -1 << endl;
break;
}
int ans = INF;
for(int i = 1;i*i<=x;i++){
if(x % i == 0){
for(int j = 0;j<20;j++){
if(c[i][j] > 0){
ans = min(ans,pcnt[x/i] + j);
}
if(c[x/i][j] > 0){
ans = min(ans,pcnt[i] + j);
}
}
}
}
cout << ans << endl;
break;
}
}
}
}
|
