平方自由数

ereoth / 2023-08-09 / 原文

Problem

多组数据。
给出一个 \(\{1,2,\cdots , n\}\) 的全集，从其中选取子集 \(S\)，满足：子集大小 \(\vert S \vert \le k\)，(至少选择一个数) \(\prod_{u\in S}u\) 是一个平方自由数(square-free integer)，即这个数的质因子幂指数均为 \(1\)。求满足条件的子集数，对 \(10^9+7\) 取模。

Input

第一行包含一个整数 \(T(T \le 5)\)，表示数据组数。

对于每组数据，每行包含两个正整数 \(n, k(n, k \le 500)\)。

Output

对于每组数据，输出一个整数，表示答案。

Sample

Input 1

2
4 2
6 4

Output 1

6
19

Solution

一个平方自由数可以表示成一些质数的乘积，因此可以考虑每一个质因数是否选择。同时发现一个很好的性质，一个 \([1,n]\) 的数最多只有一个质因子 \(\geq \sqrt{n}\) 个。所以对于 \(\sqrt{n}\) 以内的质数(\(8\) 个)，可以状压处理。然后枚举大于 \(23\) 的质数，并将它搭配好不超过 \(23\) 的若干个质因子，\(dp\) 即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int kmax = 505;
const int kmaxM = 8;
const int Mod = 1e9 + 7;

int t, n, k;
bool b[kmax];
int pr[kmax], pc;
long long fac[1 << kmaxM];
long long f[1 << kmaxM][kmax], g[1 << kmaxM][kmax], res; // 前8个质数是否选择，一共选了多少个数

void Prime() { // 筛质数
	b[1] = 1;
	for(int i = 2; i < kmax; i++) {
		if(!b[i]) {
			pr[pc++] = i;
		}
		for(int j = 0; j < pc && i * pr[j] < kmax; j++) {
			b[i * pr[j]] = 1;
			if(i % pr[j] == 0) break;
		}
	}
}

void Mul() {
	for(int i = 0; i < 1 << kmaxM; i++) {
		fac[i] = 1;
		for(int j = 0; j < kmaxM; j++) {
			if(i & (1 << j)) {
				fac[i] = fac[i] * pr[j]; // 计算乘积
			}
		}
	}
}

void Solve() {
	cin >> n >> k;
	memset(f, 0, sizeof(f));
	memset(g, 0, sizeof(g));
	f[0][0] = 1, res = 0;
	for(int i = 0; i < 1 << kmaxM; i++) {
		if(fac[i] > n) continue; // 取值不能超过n
		for(int j = k; j; j--) {
			for(int l = ((1 << kmaxM) - 1) ^ i; ; l = (l - 1) & (((1 << kmaxM) - 1) ^ i)) {
				f[l | i][j] = (f[l | i][j] + f[l][j - 1]) % Mod; // 转移
				if(!l) break;
			}
		}
	}
	for(int t = kmaxM; t < pc; t++) { // 枚举大于23的质数
		memcpy(g, f, sizeof(f));
		for(int i = 0; i < 1 << kmaxM; i++) { // 枚举前8个质数的选择情况
			if(fac[i] * pr[t] > n) continue;
			for(int j = k; j; j--) {
				for(int l = ((1 << kmaxM) - 1) ^ i; ; l = (l - 1) & (((1 << kmaxM) - 1) ^ i)) {
					f[l | i][j] = (f[l | i][j] + g[l][j - 1]) % Mod; // 转移
					if(!l) break;
				}
			}
		}
	}
	for(int i = 0; i < 1 << kmaxM; i++) {
		for(int j = 1; j <= k; j++) {
			res = (res + f[i][j]) % Mod; // 统计结果
		}
	}
	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	Prime();
	Mul();
	cin >> t;
	while(t--) { // 多组数据
		Solve();
	}
	return 0;
}