bzoj 2820 / SPOJ PGCD 莫比乌斯反演

那啥bzoj2818也是一样的,突然想起来好像拿来当周赛的练习题过，用欧拉函数写掉的。

求$(i,j)=prime$对数

\begin{eqnarray*}\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=p]&=&\sum_{p=2}^{min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[i⊥j]\newline&=&\sum_{p=2}^{min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|(i,j)}{\mu(d)}\newline&=&\sum_{p=2}^{min(n,m)}\sum_{d}^{\lfloor\frac{min(n,m)}{p}\rfloor}{\mu(d)}\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor\end{eqnarray*}

枚举质数的倍数，预处理好，最后底数优化一下。

/** @Date    : 2017-09-09 00:24:45

  * @FileName: bzoj 2820 莫比乌斯反演.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e7+20;

const double eps = 1e-8;

int pri[N];

int mu[N];

LL sum[N];

int c = 0;

bool vis[N];

void mobius()

{

	MMF(vis);

	MMF(mu);

	mu[1] = 1;

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

	{

		if(!vis[i])

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

		for(int j = 0; j < c && i * pri[j] < N; j++)

		{

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

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

			{

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

				break;

			}

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

		}

	}

	for(int i = 0; i < c; i++) //预处理 mu[dp/p]

		for(int j = 1; j * pri[i] < N; j++)

			sum[j * pri[i]] += mu[j];

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

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

}

int main()

{

	mobius();

	int T;

	cin >> T;

	while(T--)

	{

		LL n, m;

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

		LL ans = 0;

		LL mi = min(n, m);

		LL last;

		for(int i = 1; i <= mi; i = last + 1)

		{

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

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

		}

		printf("%lld\n", ans);

	}

    return 0;

}

巴特西

bzoj 2820 / SPOJ PGCD 莫比乌斯反演

最新文章

热门文章