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

我正在这样做competetive programming task,尽管我认为我有一个渐近最优的解决方案,但仍然超出了时间限制。您需要注册一个帐户才能查看问题说明并提交,所以我将在这里重新声明:

  

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

约束为1

示例:

[1,18]的解决方案是7,因为在该范围内有7个具有奇数除数的数字:

1 - (1)
2 - (1,2)
4 - (1,2,4)
8 - (1,4,8)
9 - (1,3,9)
16 - (1,8,16)
18 - (1,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,我不确定为什么。我正在寻找任何渐近改进或恒定因子优化。

kewen163 回答:[L,R]中具有奇数个奇数因子的数字数量

诀窍是要注意这些数字是正方形还是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";
    }
}
本文链接:https://www.f2er.com/3168725.html

大家都在问