最简根式

题目链接：

题目大意

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

思路

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

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

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

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

显然右边那坨是可以用整除分块加速，那一个区间的 μ ( i ) mu(i) μ(i) 之和直接上杜教筛。 不过发现右边那个还是太慢了。 不过会注意到一开始几乎每个的区间长度都是 1 1 1，那你可以把 n 1 3 n^{frac{1}{3}} n31 这个部分的 i i 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
", ans);
}

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