P1463 [SDOI2005]反素数ant

题意：

题解：

思维难度不高，考虑到n较大，而反质数个数较少

所以只要算出每个反质数即可

考虑如何计算，可以发现，我们只需枚举计算出约数有x个的最小数，再做一下判断即可

另外约数的个数=（a1+1)(a2+1)(a3+1)......

其次有三个细节需要注意

1.是对约数个数的预计，小了会造成wa

2.相应约数就会相应需要计算2^3000次方，而由于实际答案不超过2e9，所以对于那些在任何一个环节超过2e9的都不用计算

3.在2的基础上，不要将2e9扩大太多，因为在运算中有将其平方的操作

代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define INF  2999999999

#define INF2 2000000000

ll f[],b[][];

bool cmp(ll a,ll b)

{

    return(a>b);

}

ll js(ll x,ll y,ll z)

{

    if (x==) return(x);

    ll tmp=INF;

    for (ll i=y;i>;i--)

      if (x%i==)

      {

          ll tmp2=b[z][i-]*js(x/i,i,z+);

        if (tmp2!= && tmp2<=INF2) tmp=min(tmp,tmp2);

      }

    return(tmp);

}

int main(){

    ll p=;

    ll a[]={,,,,,,,,,,,,,,,};

    for (ll i=;i<=p;i++)

    {

        b[i][]=;

      for (ll j=;j<=;j++)

      {

        b[i][j]=b[i][j-]*a[i];

        if (b[i][j]>INF2) break;

        }

  }

    ll n,m=;

    cin>>n;

    for (ll i=;i<=m;i++)

    {

        f[i]=js(i,i,);

  }

  p=m;

  ll maxn=;

 // for (int i=1;i<=p;i++)cout<<f[i]<<endl;

  for (int i=p-;i>=;i--)

    f[i]=min(f[i+],f[i]);

    for (int i=p;i>=;i--)

      if (f[i]<=n)

        {

      maxn=max(maxn,f[i]);

       }

     cout<<maxn;

}