hdu5528 Count a * b

积性函数+莫比乌斯反演+枚举因子

5.HDU5528 Count a * b

题目描述

定义$f(m)$为满足$a*b \nmid m$的二元组$(a,b)$的个数，求$g(n)=\sum\limits_{m\mid n}f(m)$。

题目分析

直接求发现非常的不好求，那么我们考虑迂回战术，可以发现$ m\nmid ab$的个数根$m^2-m\mid ab$的个数一样，那么就把问题转化成了$g(n) = \sum\limits_{m|n}m^2-h(m)$，$h(m)$为$m \mid ab$的个数。因为$x^2$是一个典型的鸡性函数，$\sum\limits_{m\mid n}m^2 = (1+p_1^2+p_14+…p_1^{{2k_1})*(1+p_2}2+p_2^4+…p_2{2k_2})…(1+p_t^2+p_t4+…p_t^{2k_t})$， 考虑h(x)，对于$d = gcd(a,m)$而言，$\frac{m}{d} \mid \frac{a}{d} b = \frac{m}{d} \mid b$,因为a满足上述条件的个数为$\varphi(m/d)$那么$h(m)=\sum\limits_{d\mid m}d\cdot \varphi(m/d)$，要求的答案就是$\sum \limits_{m \mid n}\sum\limits_{d\mid m}d\cdot \varphi(m/d)=\sum\limits_{d \mid n}d\sum\limits_{\frac{m}{d} \mid \frac{n}{d}}\varphi(m/d)$根据莫反其为$\sum\limits_{d \mid n}d \cdot \frac{n}{d}=\sum\limits_{d \mid n} n$ ，这些东西都可以通过质因数分解进行求。

代码

//
// Created by mrx on 2022/9/24.
//
#include <vector>
#include <algorithm>
#include <iostream>
#include <array>

using ll = long long;
using ull = unsigned long long;


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::vector<bool> vis(4e4 + 10);
	std::vector<int> prime;
	for (int i = 2; i <= 4e4; ++i) {
		if (!vis[i])prime.push_back(i);
		for (int j = 0; j < prime.size() && i * prime[j] <= 4e4; ++j) {
			vis[i * prime[j]] = true;
			if (i % prime[j] == 0)break;
		}
	}

	int t;
	std::cin >> t;
	while (t--) {
		int n;
		std::cin >> n;
		ull ans1 = 1, ans2 = n;
		int tmp = n;
		for (int i = 0; i < prime.size() && prime[i] * prime[i] <= tmp; ++i) {
			if (tmp % prime[i] == 0) {
				int cnt = 0;
				while (tmp % prime[i] == 0)tmp /= prime[i], cnt++;
				ull cur = 1, base = prime[i] * prime[i];
				for (int j = 0; j < cnt; ++j) {
					cur += base;
					base *= (ull) prime[i] * (ull) prime[i];
				}
				ans1 *= cur;
				ans2 *= cnt + 1;
			}
		}
		if (tmp != 1)ans1 *= (1ull + (ull) tmp * (ull) tmp), ans2 *= 2ull;
		ull ans = ans1 - ans2;
		std::cout << ans << '\n';
	}
	return 0;
}