The 2022 ICPC Xinjiang Province Contest 校赛 C题

题意

多组测试数据,给定 L , R L,R L,R , 求区间 [ L , R ] [L,R] [L,R]所有数的最大开根次数 即 M K = i M^K=i MK=i

数据范围 : 1 e 18 1e18 1e18

思路

我们考虑最大开次方数即 l o g 2 N log_2N log2​N

这里可以使用换底公式得 l o g N l o g 2 \frac{logN}{log2} log2logN​

这样子我们就可以求出最大的以二为底的次幂

因为数据范围很大,我们并不能直接枚举每一个 i i i

因此考虑使用前缀和优化

设 c n t [ ] cnt[] cnt[]数组为 2 − n 2-n 2−n能开方 i i i次的个数,(默认 1 1 1的贡献是 1 1 1

然后这里就有一个结论了

从 1 − N 1-N 1−N能被开 x x x次方的数的个数为 p o w ( N , 1.0 / x ) pow(N,1.0/x) pow(N,1.0/x)

例如 : 1 − 10 1-10 1−10以内, p o w ( N , 1.0 / 3 ) = 2 pow(N,1.0/3)=2 pow(N,1.0/3)=2即 1 , 8 1,8 1,8 1 − 10 1-10 1−10以内, p o w ( N , 1.0 / 2 ) = 3 pow(N,1.0/2)=3 pow(N,1.0/2)=3即 1 , 4 , 9 1,4,9 1,4,9

显然是有重复的 1 1 1,而且考虑 16 16 16既可以开平方又可以开四次方,说明不仅有 1 1 1

显然我们是要舍去的,因为题目要求的是最大的开次方数,因此我们都选 高次方的 如 : 16 的 四 次 方 16的四次方 16的四次方

这样子我们就求出了, 2 − N 2-N 2−N中有多少可以开 i i i次方的数,

所以最后计算答案只需要 c n t [ i ] ∗ ( i − 1 ) cnt[i]*(i-1) cnt[i]∗(i−1)即可,因为每一个开次方我们都提出来一个 1 1 1

最后在加上即可

Code

const int N = 110;

int cnt[N];

int calc(int x){
	if(x = 2 ; j --){
		cnt[j] = pow(x, 1.0 / j) - 1;
		for(int k = 2 ; k * j  l >> r, l || r) {
		cout