HDU-2841 Visible Trees(莫比乌斯反演)

Visible Trees

解题思路:

实际上的答案就是1_n与1m之间互质的数的对数，写出式子就是

\(ans=\sum^{n}_{i=1}\sum^{m}_{j=1}[gcd(i,j)=1]\)

由莫比乌斯反演引理

\(\sum_{d|n}\mu(d)=\epsilon(n)=[n=1]\)将\(\epsilon(n)\)替换为\([gcd(i,j)=1]\)有

\(\sum_{d|gcd(i,j)}\mu(d)=[gcd(i,j)=1]\)

\(ans=\sum^{n}_{i=1}\sum^{m}_{j=1}[gcd(i,j)=1]=\sum^{n}_{i=1}\sum^{m}_{j=1}\sum_{d|gcd(i,j)}\mu(d)\)

现在枚举\(d\)

由于\(d\)同时是\(i,j\)的因子

\(ans=\sum^n_{d=1}\mu(d)*\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\)

后面\(\mu(d)*\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\)能数论分块做,复杂度\(O(\sqrt{n})\)

还是挺套路的

具体实现

#include <bits/stdc++.h>

using namespace std;

/*    freopen("k.in", "r", stdin);

    freopen("k.out", "w", stdout); */

// clock_t c1 = clock();

// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define de(a) cout << #a << " = " << a << endl

#define rep(i, a, n) for (int i = a; i <= n; i++)

#define per(i, a, n) for (int i = n; i >= a; i--)

#define ls ((x) << 1)

#define rs ((x) << 1 | 1)

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> PII;

typedef pair<double, double> PDD;

typedef pair<ll, ll> PLL;

typedef vector<int, int> VII;

#define inf 0x3f3f3f3f

const ll INF = 0x3f3f3f3f3f3f3f3f;

const ll MAXN = 1e6 + 7;

const ll MAXM = 1e5 + 7;

const ll MOD = 1e9 + 7;

const double eps = 1e-6;

const double pi = acos(-1.0);

ll mu[MAXN], pri[MAXN], vis[MAXN], tot = 0;

ll sum[MAXN];

void init()

{

    mu[1] = 1;

    for (int i = 2; i < MAXN; i++)

    {

        if (!vis[i])

            pri[++tot] = i, mu[i] = -1;

        for (int j = 1; j <= tot && pri[j] * i < MAXN; j++)

        {

            vis[i * pri[j]] = 1;

            if (i % pri[j] == 0)

                mu[i * pri[j]] = 0;

            else

                mu[i * pri[j]] = -mu[i];

        }

    }

    for (int i = 1; i < MAXN; i++)

        sum[i] = sum[i - 1] + mu[i];

}

ll go(int n, int m)

{

    ll ans = 0;

    int last = 0;

    for (int l = 1; l <= n; l = last + 1)

    {

        last = min((n / (n / l)), (m / (m / l)));

        ans += (sum[last] - sum[l - 1]) * (n / l) * (m / l);

    }

    return ans;

}

int main()

{

    init();

    int t;

    scanf("%d", &t);

    while (t--)

    {

        int n, m;

        scanf("%d%d", &n, &m);

        if (n > m)

            swap(n, m);

        printf("%lld\n", go(n, m));

    }

    return 0;

}

巴特西

HDU-2841 Visible Trees(莫比乌斯反演)

Visible Trees

解题思路:

具体实现

最新文章

热门文章