uva 294 ——Divisors

怼烎@ 2022-08-09 13:49 19阅读 0赞

题意：给定一个区间\[l,r\],然后问在该区间内谁的因子最多！  
  
思路：先大致分析一下，比如对于一个数12，那么可以拆分成2\*2\*3，就是对一个数分解质因数，然后你会发现在组成因子的时候，每个质因数可以选择一个，两个……一直到到该因子的指数次个，ok这就算完了，分解质因数然后依次相乘即可，等等有什么不对，都不选后者某个质因数不选也可以啊，比如因数是1，嗯对了，指数补上1然后相乘就可以了！  
  
code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    typedef long long ll;
    const int N=35010;
    int p[N],len=0,vis[N];
    
    void tab()
    {
       
        memset(vis,0,sizeof(vis));
        for (int i=2;i<N;i++)
        {
       
            if (vis[i]) continue;
            p[len++]=i;
            for (int j=i;j<N;j+=i)
                vis[j]=1;
        }
    }
    
    int cal(int n)
    {
       
        int s=1;
        for (int i=0;i<len&&p[i]<=n;i++)
        {
       
            if (n%p[i]) continue;
            int ct=1;      //初始化为1，表示不选该质因子的情况
            while (n%p[i]==0)
            {
       
                ct++;
                n/=p[i];
            }
            s*=ct;
        }
        return s;
    }
    
    int main()
    {
       
        tab();
        int T;
        scanf("%d",&T);
        while (T--)
        {
       
            int l,r;
            scanf("%d %d",&l,&r);
            int ma=0,ans;
            for (int i=l;i<=r;i++)
            {
       
                int t=cal(i);
                if (t>ma)
                {
       
                    ma=t;
                    ans=i;
                }
            }
            printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,r,ans,ma);
        }
    }