题解：CF2044E Insane Problem

思路分析

看到题目，

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

，我们可以使用等式的基本性质，将这个式子转换成

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

，我们就可以枚举出每个

k^n

，然后对

x

和

y

进行讨论。

由题可得：

$l_1 \leq x \leq r_1$ 。
$l_2 \leq y \leq r_2$ 。

所以我们可以得出

\frac{l_2}{k^n} \leq x \leq \frac{r_2}{k^n}

。所以利用我们非常一般的数学知识，其实就是求

x

的取值范围。我们可以看下图。

我们可以发现对于每个

k^n

来说，

x

的取值范围也就是答案就是

(l_1,l_2)

与

(\frac{l_2}{k^n},\frac{r_2}{k^n})

的交集。最后，我们将每个

k^n

的答案给加起来就可以了。

参考代码

~~下面可能又来到某些人最爱的部分了。~~

CPP

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int inf=2e9;
ll l1,r1,l2,r2,k;
void solve()
{
    scanf("%lld%lld%lld%lld%lld",&k,&l1,&r1,&l2,&r2);
    ll n=1,ans=0;
    while(n<=r2&&n*l1>0&&n*l1<=r2)
    {
        ll l2b,r2b;
        l2b=(l2+n-1)/n,r2b=r2/n;
        if(r2b>=l1&&r1>=l2b)
        {
            ans+=min(r2b,r1)-max(l1,l2b)+1;
        }
        
        n*=k;
    }
    printf("%lld\n",ans);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
	return 0;
}

题解：CF2044E Insane Problem

文章操作

思路分析

参考代码

相关推荐

评论

题解：CF2044E Insane Problem