【约数】魔法数

左手的ㄟ右手 2024-03-30 11:47 60阅读 0赞

[K-魔法数\_2022河南萌新联赛第（六）场：郑州大学 (nowcoder.com)][K-_2022_ _nowcoder.com]

题意：

![278611133b204eeca1f18c3bad67f6a5.png][]

思路：

一开始想的是枚举到1e6，统计所有数的约数个数，然后就不知道然后了，甚至想放到同一个数组里面然后lower\_bound

正解是：

约数个数是5个，我们考虑它的唯一分解：

如果约数由两个质因数组成，我们算它约数最少的情况，s=p1\*p2

这样构造出来的约数个数有4个：1,p1,p2,p1\*p2

而如果多一个p1，即s=p1\*p1\*p2

这样构造出来的约数个数有6个：1,p1,p1\*p1,p2,p1\*p2,p1\*p1\*p2

所以约数的质因子个数绝对不可能是2个，3，4个及以上那就更不可能了

所以约数的质因数个数只能是一个

因此约数只能是1,p1,p1^2,p1^3,p1^4，这样就是5个

所以我们筛1e3之内的质数，统计p1^4在区间\[l,r\]内的个数就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10,mxv=1e6+10;
    int len=0,l,r,ans=0;
    int prime[mxn],vis[mxv];
    void init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;prime[j]<=n/i;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        ans=0;
        cin>>l>>r;
        for(int i=1;prime[i]<=1e3;i++){
            int u=prime[i]*prime[i]*prime[i]*prime[i];
            if(u>=l&&u<=r) ans++;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        init(1e3+1e2);
        while(__--)solve();return 0;
    }

**总结：**

**当约数个数明确时，可以去考虑它的唯一分解形式。更一般地，考虑约数时，除了考虑枚举倍数的优化，也可以考虑它的唯一分解形式**

[K-_2022_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/39114/K
[278611133b204eeca1f18c3bad67f6a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5ed773d92a174c14aa5bdfbb8da49129.png