1 条题解

  • -8
    @ 2022-3-12 15:28:55
    
    先埃式筛法筛出a到b的质数。
    对于p到b(小于p的就不管了肯定不是我们要的)的质数可以另存一个数组prime[]里
    然后遍历这个数组
    模拟出prime[i]的整数倍,保证该数字大于等于a,例如prime[i]*num>=a,
    同时保证prime[i]*(num+1)<=b,然后合并这两个数字所在的集合即可。
    合并一次num++继续合并,直到不能合并为止。
    去合并下一个质数的情况。
    
    最终如何判断有几个集合
    初始化时fa[i]=i,合并完对于a到b的范围,如果fa[i]仍然等于i,那么ans++
    • 1

    信息

    ID
    920
    时间
    1000ms
    内存
    128MiB
    难度
    9
    标签
    递交数
    10
    已通过
    7
    上传者