C 序列_牛客博客

C 序列

题目是让求

Ans=\sum_{1\le x \le n,1\le y \le n}[gcd(x,y)=1]\cdot[a_{b_x}=b_{a_y}]

定义：

$F (n)$ 为 $g c d (x, y)$ 为 $n$ 的倍数的有序对的对数

$f (n)$ 为 $g c d (x, y)$ 为 $n$ 的有序对的对数

显然有

F(n)=\sum_{n|d}f(d),d是n的倍数

由莫比乌斯反演得

f(n)=\sum_{n|d}\mu(\frac{d}{n})\cdot F(d)，d是n的倍数

显然最后我们要求的答案就是 $f (1)$ ,故我们只需要预处理出来 $1\le d \le n$ 范围内 $F (d)$ 的正确答案，最后再与 $\mu(\frac{d}{1})$ 相乘求和就结束了。

从 $F (i)$ 的定义出发，我们需要枚举 $i$ 在 $1 - n$ 的所有倍数，然后去统计有多少个满足 $[a_{b_x}=b_{a_y}]$ ，就能得到 $F (i)$ 了

枚举 $1 - n$ 倍数复杂度 $O (n l o g n)$ （调和级数）

Code

const int N = 1e5 + 5;
bool vis[N];
int Primes[N], mbux[N], ct[N];
int a[N], b[N], cnt;
ll F[N];
void get_mbux(int n) {
	mbux[1] = 1;
	for (int i = 2; i <= n; i ++ ) {
		if(vis[i] == 0 ) {
			Primes[++ cnt] = i;
			mbux[i] = -1;
		}
		for (int j = 1; j <= cnt && i * Primes[j] <= n; j ++ ) {
			vis[i * Primes[j]] = 1;
			if(i % Primes[j] == 0) {
				mbux[i * Primes[j]] = 0;
				break;
			}
			mbux[i * Primes[j]] = - mbux[i];			
		}
	}
}
int main() {
	int n;
	scanf("%d", &n);
	get_mbux(n);
	for (int i = 1; i <= n; i ++ ) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i ++ ) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; i ++ ) {
		for (int j = i; j <= n; j += i) {
			ct[a[b[j]]] ++;
		}
		for (int j = i; j <= n; j += i) {
			F[i] += ct[b[a[j]]];
		}
		for (int j = i; j <= n; j += i) {
			ct[a[b[j]]] --;
		}
	}
	ll res = 0;
	for (int i = 1; i <= n; i ++ ) {
		res += mbux[i] * F[i];
	}
	printf("%lld\n", res);
	return 0;
}