[Solution][数论-GCD计数]BZOJ2818,2820

【新的问题?】

之前已经处理过一个这样的问题:求数对个数。不妨记为。可以这样计算:
它可以用来求解一个简单的问题:求数对个数。不妨记为。那么我们显然有
我们再考虑这样一个问题:求数对个数。记为
如果考虑转化到之前的问题,可以预处理所有不超过的质数,再依次使用之前的方法计算,最终求和。
不过这样做法的复杂度也许只能面对一组询问。。。

我们试着化简一下。。。

代表质数集,表示枚举的质数。

带入的计算式:

由整除运算的结合律,将后面化简:

,改为枚举:

到了这里发现可以分块预处理了。。。

,那么,怎么快速算出它呢?

注意到这是和质因子有关的,不难想到在进行欧拉筛的同时计算。

我们首先考虑,其中表示当前用来做筛法的质数,表示运行欧拉筛算法的当前变量,表示当前被筛到的数。显然此时

时,显然,那么考虑的另外一个质因子,会有,由莫比乌斯函数的定义,显然值为0.所以我们只需考虑的质因子,于是.

时,和上面考虑方法类似可得.

现在预处理函数的前缀和,再分块就可以了。回答一次询问的复杂度与之前是一样的。

下面给出裸题BZOJ2820的代码:

#include <cstdio>
#include <cstring>
#define N (10000001)
typedef long long LL;
inline int min(int a , int b) {
    return a < b ? a : b;
}
int prime[N] , top , mobius[N]; 
LL res[N];
bool notp[N];
void pre() {
    int i , j;
    mobius[1] = 1;
    res[1] = 0;
    for(i = 2 ; i <= N ; ++i) {
        if (!notp[i]) {
            res[i] = 1;
            mobius[i] = -1;
            prime[top++] = i;
        }
        for(j = 0 ; j < top ; ++j) {
            if (i * prime[j] > N)
                break;
            notp[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                mobius[i * prime[j]] = 0;
                res[i * prime[j]] = mobius[i];
                break;
            }
            else {
                mobius[i * prime[j]] = -mobius[i];
                res[i * prime[j]] = mobius[i] - res[i];
            }
        }
    }
    for(i = 2 ; i <= N ; ++i)
        res[i] += res[i - 1];
}
inline LL ans(int a , int b) {
    int now , i;
    int lim = min(a , b);
    LL ret = 0 , tmp;
    for(i = 1 ; i <= lim ; i = now + 1) {
        now = min(a / (a / i) , b / (b / i));
        ret += (res[now] - res[i - 1]) * (a / i) * (b / i);
    }
    return ret;
}
int main() {
    pre();
    int T;
    scanf("%d" , &T);
    int a , b;
    while(T--) {
        scanf("%d%d" , &a , &b);
        printf("%lld\n" , ans(a , b));
    }
    return 0;
}

还有一道和它很类似的题目,就是BZOJ2818.这道题由于具有特殊性,直接算出欧拉函数求前缀和即可。。。就不细说了。

comments powered by Disqus