hdu6715 算术 2019百度之星初赛3-1003

题目地址

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

题解

还是不会这题的容斥做法qwq。hjw当场写了个容斥A了。我推了个莫反，但是没反应过来我的式子能\(n\log n\)暴力算...

\[\begin{aligned}
&\sum_i \sum_j \mu(\frac{ij}{(i,j)})\\
&=\sum_{d} \sum_i \sum_j \mu(\frac{i}{d}) \mu(\frac{j}{d}) \mu(d) [(i,j)=d]\\
&=\sum_{d}\mu(d)\sum_i^{\frac{n}{d}} \sum_j ^\frac{m}{d} \mu(id)\mu(jd)[(i,j)=1]\\
&=\sum_{d}\mu(d)\sum_i^{\frac{n}{d}} \sum_j ^\frac{m}{d} \mu(id)\mu(jd)\sum_{k|(i,j)}\mu(k)\\
&=\sum_{d}\mu(d)\sum_{k=1}^{\frac{n}{d}} \mu(k)\sum_i^{\frac{n}{kd}} \sum_j ^\frac{m}{kd} \mu(kdi)\mu(kdj)\\
&设T=kd\\
&=\sum_T \left( \sum_{i} ^ {\frac{n}{T}} \mu(iT) \right) \left( \sum_{j} ^ {\frac{m}{T}} \mu(jT) \right)\sum_{d|T} \mu(d)\mu(\frac{T}{d})
\end{aligned}
\]

第一步就是利用了\(\mu\)是个积性函数的性质，\(i\)和\(j\)除掉\((i,j)\)后显然互质，然后再乘上\((i,j)\)即可得到\(\mu(\frac{ij}{(i,j)})\)了。

然后第二步是乘上了\(\mu^2 (d)\)（当\(d\)无平方因子时，\(\mu^2 (d)=1\)，当有平方因子时本身这一项也是\(0\)），所以可以直接乘上\(\mu^2 (d)\)而不会对式子造成影响。

最后式子三个东西全都能\(n \log n\)埃筛筛出来...总复杂度\(O(T n \log n)\)

开了long long所以可能跑的比较慢...看起来是不用开的

#include <bits/stdc++.h>

using namespace std;

namespace io {

char buf[1<<21], *p1 = buf, *p2 = buf, buf1[1<<21];

inline char gc() {

    if(p1 != p2) return *p1++;

    p1 = buf;

    p2 = p1 + fread(buf, 1, 1 << 21, stdin);

    return p1 == p2 ? EOF : *p1++;

}

#define G gc

#ifndef ONLINE_JUDGE

#undef G

#define G getchar

#endif

template<class I>

inline void read(I &x) {

    x = 0; I f = 1; char c = G();

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = G(); }

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = G(); }

    x *= f;

}

template<class I>

inline void write(I x) {

    if(x == 0) {putchar('0'); return;}

    I tmp = x > 0 ? x : -x;

    if(x < 0) putchar('-');

    int cnt = 0;

    while(tmp > 0) {

        buf1[cnt++] = tmp % 10 + '0';

        tmp /= 10;

    }

    while(cnt > 0) putchar(buf1[--cnt]);

}

#define in(x) read(x)

#define outn(x) write(x), putchar('\n')

#define out(x) write(x), putchar(' ')

} using namespace io;

#define ll long long

const int N = 1000010;

int T, n, m;

int p[N], cnt, vis[N];

ll mu[N], S1[N], S2[N], S3[N];

void init() {

	mu[1] = 1;

	for(int i = 2; i < N; ++i) {

		if(!vis[i]) p[++cnt] = i, mu[i] = -1;

		for(int j = 1; j <= cnt && i * p[j] < N; ++j) {

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

			if(i % p[j] == 0) {

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

				break;

			}

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

		}

	}

	for(int i = 1; i < N; ++i) {

		for(int j = i; j < N; j += i) {

			S3[j] += mu[i] * mu[j / i];

		}

	}

}

int main() {

	init(); read(T);

	while(T--) {

		read(n); read(m);

		for(int i = 1; i <= max(n, m); ++i) S1[i] = S2[i] = 0;

		if(n > m) swap(n, m);

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

			for(int j = i; j <= n; j += i)

				S1[i] += mu[j];

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

			for(int j = i; j <= m; j += i)

				S2[i] += mu[j];

		ll ans = 0;

		for(int i = 1; i <= n; ++i) {

			ans += S1[i] * S2[i] * S3[i];

		}

		outn(ans);

	}

}

巴特西

hdu6715 算术 2019百度之星初赛3-1003

题目地址

题解

最新文章

热门文章