2016-08-21

HDU 5812 Distance【数学】

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5812

题意：

维护一个集合，有三种操作：

插入一个数
删除一个数
给定$x$，在集合中找到一个$y$，使得$d(x,y)$最小。
其中$d(x,y)$表示$x通过乘除质数转化为y的质数操作数个数$

分析：

分析可得，对于两个数$x,y$，$d(x,y)即为两个数质因数分解后，消去相同的质因数，剩下的质因数个数和$，也就可以写成$f(x/gcd(x,y))+f(y/gcd(x,y))$，其中$f(x)$为$x$的质因数个数（注意是个数不是种类数）。
这样对于给定$x$，我们可以$\sqrt x$枚举因数，对于每个因数$y$，找到$y$的倍数$z$，使得$f(z/y)最小$，$f(z/y)+f(x/y)$的最小值即为答案。
那么如何快速的获得最小的$f(z/y)$呢？我们可以对于每个因数$y$，用$c[y][s]$记录$y$的所有倍数$z$中，满足$f(z)=s$的$z$的个数，增加的时候直接加一，删除的时候直接减一。对于$y$，找到最小的$s$即可。可以用数组记录$s$的信息，但是不能单纯的只记录最小，因为存在删除操作，而$s$最多有$20$个$(2^{20}=1048576)$，所以可以将所有可能的$s$值压一下，然后通过位运算获得最小的$s$，并进行增减操作。时间复杂度$O(Q\sqrt{x})$

代码：

/*************************************************************************
    > File Name: 5812.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/18 9:24:07
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 5, maxm = 20 + 5, oo = 0x3f3f3f3f;
int c[maxn][maxm];
int f[maxn];
bool isprime[maxn];
int prime[maxn];
int has[maxn];
int tot;
void getprime()
{
    tot = 0;
    memset(isprime, true, sizeof(isprime));
    isprime[1] = false;
    for(int i = 2; i < maxn; i++){
        if(isprime[i]){
            has[i] = 1;
            prime[tot++] = i;
            for(int j = 2 * i; j < maxn; j += i){
                isprime[j] = false;    
                int tmp = j;
                while(tmp % i == 0){
                    has[j]++;
                    tmp /= i;
                }
            }
        }
    }
}
int main (void)
{
    int kas = 1;
    int Q;
    char ch;int x;
    getprime();
    while(~scanf("%d", &Q) && Q){
        memset(f, 0, sizeof(f));
        memset(c, 0, sizeof(c));
        printf("Case #%d:\n", kas++);
        for(int i = 0; i < Q; i++){
            getchar();
            scanf("%c%d", &ch, &x);
            if(ch == 'I'){
                if(c[x][0]) continue;
                for(int i = 1; i * i <= x; i++){
                    if(x % i == 0){
                        c[x / i][has[i]]++;
                        f[x / i] |= 1 << has[i];
                        if(i * i != x){
                            c[i][has[x / i]]++;
                            f[i] |= 1 << has[x / i];
                        }
                    }
                }
            }else if(ch == 'D'){
                if(!c[x][0]) continue;
                for(int i = 1; i * i <= x; i++){
                    int cnt = 0;
                    if(x % i == 0){
                        if(c[x / i][has[i]]) c[x / i][has[i]]--;
                        if(!c[x / i][has[i]]) f[x / i] ^= 1 << has[i];
                        if(i * i != x){
                            if(c[i][has[x / i]]) c[i][has[x / i]]--;
                            if(!c[i][has[x / i]]) f[i] ^= 1 << has[x / i];
                        }
                    }
                }
            }else{
                int ans = oo;
                for(int i = 1; i * i <= x; i++){
                    if(x % i == 0 && f[x / i]){
                        ans = min(ans, __builtin_ffs(f[x / i]) - 1 + has[i]);
                    }
                    if(x % i == 0 && f[i]){
                        ans = min(ans, __builtin_ffs(f[i]) - 1 + has[x / i]);                        
                    }
                }
                if(ans == oo) ans = -1;
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}