526互联

【SSL 2402】最简根式（杜教筛）（整除分块）

发布时间 2023-03-31 09:20:40作者: あおいSakura

最简根式

题目链接：SSL 2402

题目大意

多次询问，每次给你一个 n，问你有多少个 a,b<=n 满足存在一个 k>=2 使得任意正整数 x 都有
ax+b 的 k 次开根不是最简根式。

思路

考虑对应 \(a,b\) 会有的性质。
那注意到要任意整数都有不是最简根式，而不是最简根式代表有一个因子是 \(x^k\)（\(x\geqslant 2,k\geqslant 2\)）
那注意到有 \(x^3\) 一定有 \(x^2\)（其他也类似），所以也就是需要有一个平方因子。

那因为你一直要加，所以其实你应该让 \(a,b\) 都有这个平方因子，这样它们无论怎么加起来都会有这个平方因子。
而如果不满足的话，那它们之间顶多有相同的质数，而且每个至多一次，那你把那些相当于除掉，它们就是互质的，同时也跟你除的数互质，那就能造出模你那些质数下任意的数，那比如一个 \(1\)，再让他们里面没有平方因子，就找到不满足的地方了。

那问题就变成了有多少个二元组 \((a,b)\) 满足 \(\gcd(a,b)\) 有平方因子。
考虑枚举一个符合条件的平方因子，然后数有多少个数满足，不过不同平方因子之间可能会数重。
（一个数可能会有多个平方因子）
所以要容斥，那你如果把它开根一下，假如最大的那个平方因子开根是 \(x\)，那会有的别的就是 \(y|x\)，也就是因子，那这个的容斥不难想到莫反的那个。
然后因为不能有 \(1\) 的平方，那答案就是：
\(-\sum\limits_{i=1}^{\sqrt{n}}\mu(i)\left\lfloor\dfrac{n}{i^2}\right\rfloor^2\)

那直接搞就能做到 \(O(\sqrt{n})\)，考虑优化。

显然右边那坨是可以用整除分块加速，那一个区间的 \(\mu(i)\) 之和直接上杜教筛。
不过发现右边那个还是太慢了。
不过会注意到一开始几乎每个的区间长度都是 \(1\)，那你可以把 \(n^{\frac{1}{3}}\) 这个部分的 \(i\) 暴力做，然后再整除分块。

然后就好了。

代码

#include<map> 
#include<cmath>
#include<cstdio>
#define ll long long
#define mo 998244353

using namespace std;

const int Maxn = 1e8;
ll n;
int ans;

int add(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int dec(int x, int y) {return x < y ? x - y + mo : x - y;}
int mul(int x, int y) {return 1ll * x * y % mo;}

int sumid(ll x) {
	x %= mo; return 1ll * x * (x + 1) / 2 % mo;
}
int sumI(ll x) {
	return x % mo;
}
int sum3(ll x) {
	return (x > 0);
}

int prime[Maxn + 100], rem_mus[Maxn + 100];
bool np[Maxn + 100];
map <ll, int> mp_mus;

void Init() {
	rem_mus[1] = 1;
	for (int i = 2; i <= Maxn; i++) {
		if (!np[i]) {
			prime[++prime[0]] = i;
			rem_mus[i] = -1;
		}
		for (int j = 1; j <= prime[0] && i * prime[j] <= Maxn; j++) {
			np[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
				else rem_mus[i * prime[j]] = -rem_mus[i];
		}
	}
	for (int i = 1; i <= Maxn; i++) {
		if (rem_mus[i] == -1) rem_mus[i] = mo - 1;
		rem_mus[i] = add(rem_mus[i - 1], rem_mus[i]);
	}
}

ll mus(ll now) {
	if (now <= Maxn) return rem_mus[now];
	if (mp_mus[now]) return mp_mus[now];
	ll sum = sum3(now);
	for (ll L = 2, R; L <= now; L = R + 1) {
		R = now / (now / L);
		sum = dec(sum, mul(dec(sumI(R), sumI(L - 1)), mus(now / L)));
	}
	return mp_mus[now] = sum;
}

void slove() {
	scanf("%lld", &n); ans = 0;
	ll L = 2;
	for (; L * L * L <= n; L++) ans = dec(ans, mul(mul(n / L / L % mo, n / L / L % mo), dec(mus(L), mus(L - 1))));
	for (ll R; L * L <= n; L = R + 1) {
		R = floor(sqrt(n / (n / L / L)));
		ans = dec(ans, mul(mul(n / L / L % mo, n / L / L % mo), dec(mus(R), mus(L - 1))));
	}
	printf("%d\n", ans);
}

int main() {
	freopen("math.in", "r", stdin);
	freopen("math.out", "w", stdout);
	
	Init();
	
	int T; scanf("%d", &T);
	while (T--) slove();
	return 0;
}