和式变换技术

放一下引用的大佬博客地址 https://www.eriktse.com/algorithm/1101.html#toc-12

自己做一下备份~

阅读本文章所需前置知识：

• 整数分块
• 莫比乌斯反演

实战部分

  在和式变换中，莫比乌斯反演与欧拉函数常和 $gcd$ 结合出现。$gcd(x, y) == 1$形式的为莫比乌斯反演，$gcd(x, n) == 1$形式的为欧拉函数。

1、P3455 [POI2007]ZAP-Queries

https://www.luogu.com.cn/problem/P3455

结合和式变换与莫比乌斯反演。

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL; 
const int N = 5e4 + 10;
int primes[N], cnt;
bool st[N];
int mu[N];
LL s[N];
int n; 

void init(int n){
	mu[1] = 1;
	for(int i = 2; i <= n; i++){
		if(!st[i]) primes[cnt++] = i, mu[i] = -1;
		for(int j = 0; primes[j] <= n / i; j++){
			st[primes[j] * i] = true;
			if(i % primes[j] == 0) break;  //此处i是primes[j]的质因子，因此i * primes[j]一定有某个质因子>=2个 
			mu[primes[j] * i] = -mu[i];  //说明primes[j]不是i的质因子，因此不同的质因子数量+1 
		}
	}
	for(int i = 1; i <= n; i++) s[i] = s[i - 1] + mu[i];
}

void solve(){
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i++){
		int a, b, d;
		scanf("%d%d%d", &a, &b, &d);
		if(a > b) swap(a, b);
		LL ans = 0;
		for(int l = 1, r; l <= a / d; l = r + 1){
			r = min((a / d) / (a / (d * l)), (b / d) / (b / (d * l)));
			ans += 1LL* (a / (d * l)) * (b / (d * l)) * (s[r] - s[l - 1]);	
		}
		printf("%lld\n", ans);
	}
}
 
int main(){
	int T = 1;
//	scanf("%d", &T);
	init(N - 1);
	while(T -- ){
		solve();
	}
}

2、hx的数列

https://ac.nowcoder.com/acm/contest/47681/I

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL; 
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
int phi[N];
LL n;

void init(int n){
	phi[1] = 1;
	for(int i = 2; i <= n; i++){
		if(!st[i]) primes[cnt++] = i, phi[i] = i - 1;
		for(int j = 0; primes[j] <= n / i; j++){
			st[primes[j] * i] = true;
			if(i % primes[j] == 0){
				phi[primes[j] * i] = phi[i] * primes[j];
				break;
			}
			else phi[primes[j] * i] = phi[i] * (primes[j] - 1);
		}
	}
} 

void solve(){
	scanf("%lld", &n);
	LL t = sqrtl(n);
	LL ans = 0;
	for(LL i = 2; i <= t; i++) ans += (n / i / i) * phi[i];
	printf("%lld\n", ans);
}
 
int main(){
	int T = 1;
//	scanf("%d", &T);
	init(N - 1);
	while(T -- ){
		solve();
	}
}