HDU5812 Distance

11 May 2019 | duanyll | Tags: OI 题解 数论

题意

给出一个空集合和三个操作。操作I向集合中插入元素X，操作D删除集合中的元素X，操作Q，查询集合中的所有元素与X的最小距离是多少？

定义最小距离$d(x,y)$为从x变为y只通过乘或者除素数所需要的最少操作次数。例如：$d(15,50)=3$，因为 $15\div 3\times 2\times 5=50$

分析

定义$pfac(x)$表示x的质因数个数，易知

\[d(a,b) = pfac(\frac{a}{gcd(a,b}) + pfac(\frac{b}{gcd(a,b)})\]

由于$a_i \leq 1000000$，所以可以预处理出pfac。

对于每次查询，可以暴力枚举x的因数作为两数的GCD，($O(\sqrt {a_i})$)，然后再枚举这个GCD的倍数作为另外一个数，判断这个数在集合里面是否存在，再更新ans。

但是这样跑不过。考虑到$pfac(a_i)$不会超过20，聪明一些的做法是开一个数组cnt[i][j]，表示当前集合中满足含有因数i，同时含有的除了i后质因数数量是j的数的数目，就可以在插入和删除时$O(\sqrt {a_i})$维护cnt数组，查询时对于x的每一个因数枚举j就完了。总时间复杂度$O(q \sqrt{a_i} \times 20)$

代码

#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;
			}
		}
	}
}