http://acm.hdu.edu.cn/showproblem.php?pid=5812
题目的询问是给一个Q,X ，在给出的集合里找到一个y满足d(x,y)最小。
1、首先素筛预处理出ans[i]，表示i能分解成的质因数个数。
2、要从x变成y，就是从x出发去掉x独有的素因子（gcd），再加上所有y的独有的素因子。
3、所以题意的d(x,y)可以简要地表示为 d(x,y)= ans[x/gcd] + ans[y/gcd]， 其中的gcd是指的 gcd(x,y)即她俩的公约数
4、那么对于每一次询问 Q X， 我们可以大胆放心地枚举X的所有约数i，也即当作i即为d(x,y)的gcd， 对于答案 d(x,y)= ans[x/gcd] + ans[y/gcd]，既然我们枚举了gcd，那么接下来就是要找 对于这个gcd下，枚举y咯（是不是很暴力啊啊啊）
5、我们需要（暴力）维护一个表int c[MAX][20];//c[i][j]表示i的倍数Y,满足ans[Y/i]==j的数量
由于数最大也就是1000000，不超过2^20,所以第二维开20够了。
每次操作都要分解质因素，复杂度sqrt(x)，总复杂度q*sqrt(x)
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <queue> #include <deque> #include <set> #include <vector> using namespace std; typedef long long ll; const int MAX=1000000; bool f[MAX+50]; int ans[MAX+50]; int c[MAX][20];//c[i][j]表示i的倍数Z,满足[Z/i]==j的数量 set<int >sb; set<int >::iterator it; void pre1() { f[1]=true; for (ll i=2; i<=MAX; i++) { if (f[i]==false) { ans[i]=1; for (ll j= i+i; j<=MAX; j=j+i) { f[j]=true; if (j%i==0) ans[j]=ans[j/i]+1; } } } } void add(int x,int times) { for (int i=1; i*i<=x; i++) { if (x%i==0) { c[i][ans[x/i]]+=times; if (i!=x/i) c[x/i][ans[i]]+=times; } } } int main() { pre1(); int n; int cnt=1; while(scanf("%d",&n)!=EOF&&n) { for (it=sb.begin();it!=sb.end();it++) add(*it,-1); sb.clear(); printf("Case #%d:\n",cnt++); char op[5]; int x; for (int i=1; i<=n; i++) { scanf("%s%d",op,&x); if (op[0]=='I') { if (!sb.count(x)) add(x,1),sb.insert(x); } else if (op[0]=='D') { if (sb.count(x)) add(x,-1),sb.erase(x); } else { if(sb.empty()) { printf("-1\n");continue; } int num=1e9; for (int j=1; j*j<=x; j++) //枚举gcd-约数 { if (x%j==0) { for (int k=0; k<20; k++) { if (c[j][k])//表示j(gcd)的倍数Z且 ans[z/j]==k num=min(num,ans[x/j]+k); if (c[x/j][k]) num=min(num,ans[j]+k); } } } printf("%d\n",num); } } } return 0; }
