[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的数量。

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

typedef long long ll;
// number of numbers matching criteria on [1, n]
ll n_under(ll n){
    ll res = 0;
    while(n){
        res += (sqrt(n) + 1ll)/2ll;
        n /= 2ll;
    }
    return res;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    cin >> q;
    for(int i = 1; i <= q; ++i){
        ll l, r;
        cin >> l >> r;
        cout << "Case " << i << ": " << (n_under(r) - n_under(l - 1)) << endl;
    }
    return 0;
}

我在第一个测试集中遇到了TLE问题，但不确定原因。我正在寻找任何渐近改进或常数优化。

- Primusa

---

@Evg，考虑到[L,R]达到了10^18，我认为这很不可能。也许我们可以重复使用平方根？但是制造对立的例子非常容易，如果所有查询都不重叠且高于10^17，会怎么样呢？ - Primusa

为什么2、4和8不是解的一部分，因为它们也有奇数个奇约数？ - Wander3r

@Wander3r，你说得完全正确！16也是解集的一部分。问题已经相应地进行了编辑。 - Primusa

这行代码 res += (sqrt(n) + 1ll)/2ll 怎么解释？我不太理解。 - lincr

@lincr 它计算O的数量。因此，N已经被除以2到任何一个数了，我们取平方根来找出N下方的平方数的数量。然后，我们提取奇数的数量。 - Primusa

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

- Photon