[L, R] 中具有奇数个奇数因数的数字数

Question

我正在做这个竞争性编程任务，即使我认为我有一个渐近最优的解决方案，但我仍然超出了时间限制。需要注册账号才能看到问题说明并提交，这里我再重申一遍：

给定一个范围 [L, R]，找出该范围内具有奇数个奇数除数的整数的数量。

约束是 1 <= L <= R < 10^18，并且最多有 10^5 个这样的查询。

例子：

的解[1, 18]是 7，因为在该范围内有 7 个具有奇数个奇数除数的数字：

1 - (1)
2 - (1, 2)
4 - (1, 2, 4)
8 - (1, 2, 4, 8)
9 - (1, 3, 9)
16 - (1, 2, 4, 8, 16)
18 - (1, 2, 3, 6, 9, 18)

我的代码和想法：

我们知道除数是成对出现的，因此任何具有奇数个除数的奇数都必须是平方数。任何具有奇数除数的偶数都必须有一些奇数的“底数”，该“底数”具有奇数个除数，而要使这个“底数”做到这一点，它必须是前面讨论过的平方数。

本质上，我们正在寻找形式为 的数字O^2 * 2^N，其中O是一些奇数。我将解决方案[L, R]视为[1, R] - [1, L)，然后遍历所有内容2^N并获得O可以适合该数字的数量。

1 - (1)
2 - (1, 2)
4 - (1, 2, 4)
8 - (1, 2, 4, 8)
9 - (1, 3, 9)
16 - (1, 2, 4, 8, 16)
18 - (1, 2, 3, 6, 9, 18)

我得到了第一个测试集的 TLE，我不确定为什么。我正在寻找任何渐近改进或常数因子优化。

Answer 1

诀窍是注意这些数字要么是平方，要么是 2*平方。（或者找到前几个这样的数字并检查OEIS）

知道了这一点，我们就可以轻松地在 O(1) 时间内计算出此类数字的计数，这样我们就可以在 O(Q) 时间内回答所有查询。

1. 首先，为了计算范围 [L,R]，我们可以计算范围 [0,R] - [0,L-1]

2. 对于某些范围 [0,X]，我们可以注意到该区间内有 sqrt(X) 个方格

3. 与双平方类似，大约有 sqrt(X/2) 这样的数字

4. C++ 中大数的 sqrt 并不那么精确，因此我们可能需要为 sqrt 计算添加一些 +-1

示例代码（C++）：

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll solve(ll x)
{
    ll sq = sqrt(x)+2;
    while(sq*sq > x)sq--;

    ll sq2 = sqrt(x/2)+2;
    while(2*sq2*sq2 > x)sq2--;

    return sq + sq2;
}

ll solve(ll l, ll r)
{
    return solve(r) - solve(l-1);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll q,l,r,cs=1;
    cin>>q;
    while(q--)
    {
        cin>>l>>r;
        cout<<"Case "<<cs++<<": "<<solve(l,r)<<"\n";
    }
}