K-魔法数_2022河南萌新联赛第（六）场：郑州大学 (nowcoder.com)
题意：
思路：
一开始想的是枚举到1e6，统计所有数的约数个数，然后就不知道然后了，甚至想放到同一个数组里面然后lower_bound
正解是：
约数个数是5个，我们考虑它的唯一分解：
如果约数由两个质因数组成，我们算它约数最少的情况，s=p1*p2
这样构造出来的约数个数有4个：1,p1,p2,p1*p2
而如果多一个p1，即s=p1p1p2
这样构造出来的约数个数有6个：1,p1,p1p1,p2,p1p2,p1p1p2
所以约数的质因子个数绝对不可能是2个，3，4个及以上那就更不可能了
所以约数的质因数个数只能是一个
因此约数只能是1,p1,p1^2,p1^3,p1^4，这样就是5个
所以我们筛1e3之内的质数，统计p1^4在区间[l,r]内的个数就好了
Code：
#include
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>l>>r;
for(int i=1;prime[i]=l&&u>__;
init(1e3+1e2);
while(__--)solve();return 0;
}
总结：
当约数个数明确时，可以去考虑它的唯一分解形式。更一般地，考虑约数时，除了考虑枚举倍数的优化，也可以考虑它的唯一分解形式
Original: https://blog.csdn.net/weixin_62528401/article/details/128425475
Author: lamentropetion
Title: 【约数】魔法数
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/786781/
转载文章受原作者版权保护。转载请注明原作者出处！