题解 P1221 【最多因子数】

无尽 · 2017-09-19 22:08:06 · 题解

这是一道需要有些技巧的搜索题

数字的因子数，不一定要因数分解，

可以使质因数相乘，得到数字；

所以只需搜索质因数即可；

然后记录数字的因数数字个数，找出其拥有最大个数因数数字即可

我们学校考试时写的，有点乱...别在意

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int num,ans,l,r,Max;
int a[50000];
bool notprime[100000];
int b[50000],c[50000];
void hhh()//求出其质数
{
  for(int i=2;i<=40000;i++)//之所以是40000，因为30000平方小于1000000000而40000平方大于
    {
      if(!notprime[i])
    {
      a[++num]=i;
      int j=i<<1;
      while(j<=40000)
        {
          notprime[j]=true;
          j+=i;
        }
    }
    }
}
void dfs(long long h,long long ji,long long noww)//搜索
{
  int i,t;
  long long x;
  if(h>num) return;
  if(ji>r) return;
  t=int(log(r/double(ji))/log(double(a[h])));
  if(noww*(1<<t)<ans) return;
  if(ji>=l&&(noww>ans||(noww==ans&&ji<Max)))
    {
        ans=noww;
        Max=ji;
    }
  x=1;
  for(i=1;i<=t;i++) x*=a[h];
  for(i=t+1;i>=1;i--)
    {
      dfs(h+1,ji*x,noww*i);
      x/=a[h];
    }
}
int main()
{
  freopen("divisors.in","r",stdin);
  freopen("divisors.out","w",stdout);
  scanf("%d%d",&l,&r);
  if(l==1&&r==1)
    {
      Max=1;
      ans=1;
    }
  else
    {
      if(r-l>=10000)//这是正解
    {
      hhh();
      dfs(1,1,1);
    }
      else//怕正解错而打的暴力
    {
      for(int i=l;i<=r;i++)
        {
          int tem=2;
          for(int j=2;j*j<=i;j++)
        {
          if(j*j==i) tem++;
          else if(i%j==0) tem+=2;
        }
          if(tem>ans)
        {
          ans=tem;
          Max=i;
        } 
        }
    }
    }
  printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,r,Max,ans);
  return 0;
}