CF955C Sad powers

Luogu CF955C

题面翻译

给你 \(q\) 个询问，每次询问 \([l,r]\) 这个区间内满足 \(x=a^p(a>0,p>1)\) 的 \(x\) 的数量。

数据范围：

• \(1\leqslant q\leqslant 10^5\)。
• \(1\leqslant l\leqslant r\leqslant 10^{18}\)。

Translated by Eason_AC
2021.10.8

题目描述

You're given \(Q\) queries of the form \((L,R)\) .

For each query you have to find the number of such \(x\) that \(L<=x<=R\) and there exist integer numbers \(a>0\) , \(p>1\) such that \(x=a^{p}\) .

输入格式

The first line contains the number of queries \(Q\) \((1<=Q<=10^{5})\) .

The next $ Q $ lines contains two integers \(L\) , \(R\) each \((1<=L<=R<=10^{18})\) .

输出格式

Output \(Q\) lines — the answers to the queries.

样例 #1

样例输入 #1

6
1 4
9 9
5 7
12 29
137 591
1 1000000

样例输出 #1

2
1
0
3
17
1111

提示

In query one the suitable numbers are \(1\) and \(4\) .

Solution

2023 春赛观光团。

对于一个询问 \([l,r]\)，显然可以拆成 \([1,r]-[1,l-1]\) 两部分计算。

考虑 \([1,n]\) 如何计算。由于指数的值域很小，因此可以考虑枚举指数来计算答案。

记 \(f_i\) 表示满足 \(a_i\le n\) 的数量（不考虑与其他指数重复的情况），那么显然可以得知 \(f_i=\sqrt[i]{n}\)。考虑如何容斥掉重复的部分，直接容斥貌似不好做，因此考虑钦定一个数的唯一指数表示方式。

对于一个数 \(t\)，假设 \(t=a_1^{p_1}=a_2^{p_2}(p_1>p_2)\)，那么将 \(t\) 的表示方法钦定为 \(t=a_1^{p_1}\)，即指数最大的一个。容易发现，对于所有可以组成 \(t\) 的指数 \(p\) 都有 \(p_i \mid p_1\)。那么按照这种钦定方法下，记每个指数对答案的贡献是 \(\text{ans}_i\)，那么有 \(\text{ans}_i=f_i-\displaystyle \sum\limits_{i\mid j}\text{ans}_j\)。从大到小计算即可。时间复杂度是 \(\mathcal O(\log^2 n)\) 级别的。

代码实现的时候有一个很麻烦的东西，就是 \(\sqrt[i]{n}\) 如何计算。如果使用 \(n^{1/i}\) 计算会出现很大的精度问题；如果用二分计算的话时间会超时。因此有一个折中的办法，就是先用 \(n^{1/i}\) 计算，然后再暴力判断计算出来的这个值 \(v\) 接近的值是否满足答案，即判断一下 \(v+1,v-1,v+2,v-2,\dots\) 是否符合条件，然后卡一下精度就过了。

Code

#include<bits/stdc++.h>
#define int long long

using namespace std;

int l, r;
int a[100005];

inline long double Qpow(int x, int y) {
	long double res = 1, base = x;
	
	for (; y; y >>= 1, base *= base) {
		if (y & 1) {
			res *= base;
		}
	}
	
	return res;
}

inline int GetRoot(int x, int y) {
	int v = powl(x, (long double)1.0 / y + 1e-9);
	
	if (Qpow(v + 1, y) < x) 
		for (++v; Qpow(v + 1, y) < x; ++v);
		
	if (Qpow(v, y) > x)
		for (--v; Qpow(v, y) > x; --v);
	
	return v;
}

int Calc(int n) {
	if (n == 0) return 0;
	
	int res = 1;
	int lim = 0;
	
	for (int i = 2; ; ++i) {
		int v = GetRoot(n, i);
		lim = i;
		
		if (v <= 1) break;
		
		a[i] = v - 1;
	}
	
	for (int i = lim - 1; i >= 2; --i) {
		for (int j = i + i; j < lim; j += i) {
			a[i] -= a[j];
		}
	}
	
	for (int i = 2; i < lim; ++i) {
		res += a[i];
	}
	
	return res;
}

void Solve() {
	cin >> l >> r;
	cout << Calc(r) - Calc(l - 1) << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T; cin >> T;
	
	while (T--) Solve();
}