从a变到b，也就是将a一直除素因子，除到1为止，然后乘b的素因子，一直乘到b。
但是gcd(a,b)部分是不用除下去的。所以d(a,b)=a/gcd(a,b)的素因子个数+b/gcd(a,b)的素因子个数。
然后....脑洞开始......
枚举这个因子P，然后去计算a/P的素因子个数+b/P的素因子个数 最小值，也就是要在集合中寻找到一个b，使得式子取得最小值。
然后....可以搞一个数组 c[因子][素因子个数]=多少种情况 来存储集合中的信息。 然后删除，插入的时候维护这个数组即可。具体看看代码。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=1000010; int f[maxn],c[maxn][22],fac[maxn],sz; bool m[maxn]; queue<int>Q; bool prime(int x) { if(x==1) return 0; for (int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; } void pre() { memset(f,0,sizeof f); for(int i=2;i<=1000000;i++) { if(!prime(i)) continue; f[i]=1; int u=i+i; while(u<=1000000) { int t=u; while(t%i==0) f[u]++,t=t/i; u=u+i; } } } void get(int x) { sz=0; for(int i=1;i*i<=x;i++) { if(x%i!=0) continue; int x1=i,x2=x/i; fac[sz++]=x1; if(x2!=x1) fac[sz++]=x2; } } void Insert(int x) { m[x]=1; get(x); for(int i=0;i<sz;i++) c[fac[i]][f[x/fac[i]]]++; } void Delete(int x) { m[x]=0; get(x); for(int i=0;i<sz;i++) c[fac[i]][f[x/fac[i]]]--; } void Find(int x) { int ans=60; get(x); for(int i=0;i<sz;i++) for(int j=0;j<=20;j++) if(c[fac[i]][j]) ans=min(ans,j+f[x/fac[i]]); if(ans==60) ans=-1; printf("%d ",ans); } int main() { pre(); int cas=1,n; while(~scanf("%d",&n)) { if(n==0) break; printf("Case #%d: ",cas++); memset(c,0,sizeof c); memset(m,0,sizeof m); for(int i=1;i<=n;i++) { char op[5]; int x; scanf("%s%d",op,&x); if(op[0]=='I') { if(m[x]) continue; Insert(x); } else if(op[0]=='D') { if(!m[x]) continue; Delete(x); } else Find(x); } } return 0; }