题意
给出一个空集合和三个操作。操作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; } } } }
|