题解：CF2044E Insane Problem

分析

我们先将

\frac{y}{x}=k^n

转化为

x=\frac{y}{k^n}

。

题目说了

1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9

，也就是说

1 \leq x, y \leq 10^9

。那么我们算一下，当

k

取

\mathtt2

时，

n

最大约为

30

。我们可以枚举

n

，算出当前

x

的取值区间以及

y

的取值区间，再将两个区间的交集累加入答案中。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		int k,l1,r1,l2,r2,sum=0,asd=1;
		cin>>k>>l1>>r1>>l2>>r2;
		for(int i=0;r2/asd>=l1;i++){
			int num=max(0,min(r1,r2/asd)-max(l1,(l2-1)/asd+1)+1);
			asd*=k,sum+=num;
		}
		cout<<sum<<"\n";
	}
	return 0;
}

题解：CF2044E Insane Problem

文章操作

题解：CF2044E Insane Problem

分析

代码

相关推荐

评论

题解：CF2044E Insane Problem