专栏文章

题解：CF2044E Insane Problem

封封禁用户
CF2044E题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipten0l
此快照首次捕获于
2025/12/03 17:38
3 个月前
此快照最后确认于
2025/12/03 17:38
3 个月前
查看原文
题意很清楚，这里不再阐述，这是一道推公式的题目。

思路

由题意，
yx=kn\frac{y}{x}=k^n
两边同时乘 xx 再除以 knk^n
ykn=x\frac{y}{k^n}=x
由于 l2≤y≤r2l_2 \le y \le r_2 ，所以
l2kn≤x≤r2kn\frac{l_2}{k^n} \le x \le \frac{r_2}{k^n}
那么很简单，枚举 nn ，求出上不等式与 l1≤x≤r1l_1 \le x \le r_1 的交集之和，但是代码里需要对 l2kn\frac{l_2}{k^n} 和 r2kn\frac{r_2}{k^n} 进行上取整和下取整。
什么？你问我交集怎么求？设两不等式 l1≤x≤r1l_1 \le x \le r_1 和 l2≤x≤r2l_2 \le x \le r_2 求他们的交集很简单，就是 max⁡(min⁡(r1,r2)−max⁡(l1,l2),0)\max(\min (r_1,r_2) - \max(l_1,l_2), 0) 。
那代码就很简单了，但是注意细节。

code

CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, k, l1, r1, l2, r2;
int main(){
	cin >> T;
	while (T--){
		cin >> k >> l1 >> r1 >> l2 >> r2;
		ll sum = 0, ksm = 1ll;
		for (ll i = 0; r2 / ksm >= l1; i++) sum += max(0ll, min(r1, r2 / ksm) - max(l1, (l2 - 1ll) / ksm + 1) + 1ll), ksm *= k;
		cout << sum << endl;
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...