题解：CF2044E Insane Problem

· · 题解

思路分析

看到题目，\frac{y}{x} = k^n，我们可以使用等式的基本性质，将这个式子转换成 \frac{y}{k^n} = x，我们就可以枚举出每个 k^n，然后对 x 和 y 进行讨论。

由题可得：

所以我们可以得出 \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 的答案给加起来就可以了。

参考代码

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

#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;
}