Cydiater

「BZOJ 2671」calc

询问在$[1, N]$内,有多少对$i, j(i < j)$满足$i + j | ij$。

首先,我们设$d = (i, j)$,然后可以得到$i=ad,j=bd$,即原式变成$(a + b)d|abd^2$,即$a + b | abd$,然后因为$(a,b) = 1$,所以$(a + b, a) = (a + b, b) = 1$,所以上式就变成$a + b | d$,再设$d = t(a + b)$。即询问有多少对$(a, b, t)$,满足$a < b,(a, b) = 1, t(a + b)b \leq N$。

我们发现$b$的范围是在$\sqrt N$以内的,所以我们枚举$b$,然后又因为$\frac{N}{b(a + b)}$有$\sqrt N$个不同的取值,然后我们只需要统计某个范围内有多少个数和$b$互质就行了,简单容斥一下就行了。

啥,你说复杂度不对?

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 1e5 + 5;
const int LIM = 1e5;

int prime[MAXN], miu[MAXN], cnt = 0;
bool vis[MAXN];
ll n;

ll cal(int le, int ri, int b){
    int m = sqrt(b);
    ll sum = 0;
    up (i, 1, m) if (b % i == 0) {
        int o = i;
        sum += 1LL * (ri / o - (le - 1) / o) * miu[o];
        if (i * i != b) {
            o = b / i;
            sum += 1LL * (ri / o - (le - 1) / o) * miu[o];
        }
    }
    return sum;
}

ll calc(int b){
    int o;
    ll sum = 0;
    for (int a = 1; a < b && 1LL * (a + b) * b <= n; a = o + 1) {
        o = (n / (n / ((a + b) * b))) / b - b;
        cmin(o, b - 1);
        sum += cal(a, o, b) * (n / ((a + b) * b));
    }
    return sum;
}

int main(){
    ll ans = 0;
    scanf("%lld", &n);
    miu[1] = 1;
    up (i, 2, LIM) {
        if (!vis[i]) {
            prime[++cnt] = i;
            miu[i] = -1;
        }
        up (j, 1, cnt) {
            if (1LL * i * prime[j] > LIM) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
            miu[i * prime[j]] = -miu[i];
        }
    }
    int m = sqrt(n);
    up (i, 1, m) ans += calc(i);
    printf("%lld\n", ans);
    return 0;
}