P9611 题解

zhuweiqi · 2023-09-08 20:49:54 · 题解

一眼数论题。

观察到数据范围是 m\leq 10^{12}，因此我们需要使用 O(\sqrt{m}) 及以下时间复杂度的做法才能通过，首先考虑 O(m) 的筛倍数法，即枚举每个因数 i，找到最小的 L 和 R 使得 n\leq i\times L 并且 i\times R\leq m，这意味着范围内一共有 R-L+1 个数有 i 这个因数，然后考虑优化，我们在枚举因数 i 的时候可以顺便把 L 至 R 范围内的所有正整数也当成因数把贡献值加上，这样一来，由于约数总是成对出现的，我们只需要枚举所有不大于 \sqrt{m} 的因数，那些大于 \sqrt{m} 的因数就自然而然地也会被筛一遍了，我们的时间复杂度就可以降为 O(\sqrt{m}) 了，考虑到当 x 是完全平方数时因数 \sqrt{x} 会被重复计算两次，故我们需要将贡献值减去范围内的完全平方数的个数。参考代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll l,r,L,R,ans=0;
    scanf("%lld%lld",&l,&r);
    for(ll i=1;i*i<=r;i++) if(i*i>=l) ans--;
    for(ll i=1;i*i<=r;i++){
        l=max(l,i*i);
        L=(l+i-1)/i;
        R=r/i;
        if(L<=R) ans+=(R-L+1)<<1;
    }
    printf("%lld",ans);
    return 0;
}