HDU 5750 Dertouzos（数论）

谁借莪１个温暖的怀抱￠ 2022-07-20 12:15 109阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5750

题目大意：x能整除n，x就是n的positive proper divisor，但n本身不算，给你两个数n和d，找出所有小于n的数中，最大positive proper divisor是d个数,T组测试数据。

解题思路：很明显对于每个数x，找出其最小素数m，如果x/m等于d，那么x的最大positive proper divisor就是d，如果这样枚举小于n的每一个数，总共需要 T n √n的时间。  
还有更优的做法，我们可以直接素数筛筛出所有的素数，另每个素数x乘d，x一定小于min（d，(n-1)/d）

分两种情况，第一种情况是d是素数，我们只要枚举素数x就好，如果x小于d且x×d小于n就答案+1，否则终止循环。

第二种情况是d不是素数，我们假设d=5×7×11，很明显当  
n=2 ×5×7×11 或者n=3×5×7×11 或 n= 5 ×5×7×11都可以  
，如果n= 7×5×7×11的话，d=7×7×11,就不满足条件，所以我们可知，我们枚举的素数小于等于d的最小素数就好了。操作跟一种情况一样，加上一句如果d%x==0且x！=d，break，就好了，这种说明d不是素数，小于d的素数已经被计算过。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9+7;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int vis[1000000];
    
    LL ans=0;
    
    vector<LL> vv;
    
    int main()
    {
    
        memset(vis,0,sizeof(vis));
        for(LL i=2; i<=1000000; i++)
        {
            if(!vis[i])
            {
                for(LL j=i*i; j<=1000000; j+=i)
                {
                    vis[j]=1;
                }
            }
        }
    
        for(int i=2; i<1000000; i++)
            if(!vis[i]) vv.push_back(i);
    
        int T;
        RI(T);
        while(T--)
        {
            LL n,d;
    
            scanf("%I64d %I64d",&n,&d);
    
            ans=0;
    
            for(int i=0; i<vv.size(); i++)
            {
                LL x=vv[i];
                if(x<=d&&x*d<n) ans++;
                if(x>d) break;
                if(x*d>=n) break;
                if(d!=x&&d%x==0) break;
            }
            cout<<ans<<endl;
    
        }
        return 0;
    }