Master of Phi迪利克雷卷积代码实现

Z时代
2024-01-10
分类：技术分享

题目描述

思路

函数写为φ(d)frac{n}{d}，可以看为两个函数φ(x)和f(x)=x的迪利克雷卷积，而两个函数都是积性函数（欧拉函数需要互质的条件，不妨把这个条件也加到线性函数上）。两个积性函数卷积也是积性函数，那么我们可以把计算过程拆为m个p^q来看。化简后得到p^(q-1) p pq - q，乘起来即可。

代码实现

#include
using lint = longlong;
const lint mod = 998244353LL;
lint quickPow(const lint& base, lint pow){
	lint res = 1, temp = base;
while (pow) {
if (pow & 1) {
			res = (res * temp) % mod;
		}
		temp = (temp * temp) % mod;
pow >>= 1;
	}
return res;
}
voidrun(){
int total;
scanf("%d", &total);
	lint res = 1;
for (int i = 0; i < total; i  ) {
		lint base, pow;
scanf("%lld%lld", &base, &pow);
		lint temp = (base - pow   base * pow) % mod;
		temp = (temp * quickPow(base, pow - 1)) % mod;
		res = (res * temp) % mod;
	}
printf("%lldn", res);
}
intmain(){
int gp;
scanf("%d", &gp);
for (int i = 0; i < gp; i  ) {
		run();
	}
return0;
}