首页 > 代码库 > HDU4542 小明系列故事——未知剩余系

HDU4542 小明系列故事——未知剩余系

2024-07-12 21:51:03   214人阅读

大赞的数论题；

大致思路：

          对于TYPE=1的情况，认为　　　　X 中有　　X-K个约数，求最小的X，X-K>0 那么化为B+K的约数为B，

               我们知道（B+K)的约数<=2*SQRT(B+K);这个应该知道，

              再化简一下：B*B<=4(B+K),可以直接枚举B，有人担心会TLE，我们再证明一下：

                                                                                                        化简得 :B*B-4*B+4<=4*K+4;然后K<=47777,所以可以枚举了。。

       对于TYPE=0的情况， 我们可以预先求出有X个数的最小数，因为根据求约数个数的方程N=a[1]^x1+a[2]^x2.....;

                           num=(1+x1)*(1+x2)*。。。。；

           这里我们可以DFS搜索出来。具体看看代码应该能明白

#include<cstdio>#include<algorithm>#include<cmath>#include<string.h>typedef long long ll;using namespace std;#define maxn 200000const long long inf=(1ll<<62)+1;int prime[maxn];ll a[maxn*10];int b[maxn*2],t;void pri(){    for (int i=2;i*i<maxn;i++)        if (!b[i])        for (int j=i*2;j<maxn;j+=i)        b[j]=1;     for (int i=2;i<maxn;i++)        if (!b[i]) prime[++t]=i;   }int get(ll x){    int ans=1;    ll tmp=x;    for (int i=1;prime[i]<=tmp/prime[i];i++)    {            ll t=1;            while (tmp%prime[i]==0)            {                t++;                tmp/=prime[i];            }           if (t>1) ans*=t;        }    if (tmp!=1) ans*=2;    return ans;}void dfs(int i,ll x,int n)//DFS部分{   if (n>47777) return;   if (x<inf&&(a[n]==0||a[n]>x)) a[n]=x;//类似DP的思想   for (int j=1;j<=62;j++)   {       if (inf/prime[i]<x) break;//防止溢出，       x*=prime[i];       if (x>=inf) break;       dfs(i+1,x,n*(j+1));       }}void solve1(int x){      if (a[x]!=0) printf("%I64d\n",a[x]);      else printf("INF\n");  }void solve(ll x){    ll num=1;    while (num*num<=(num+x)*4)    {        if (num==get(num+x)) {printf("%I64d\n",num+x);return; }        num++;    }    printf("Illegal\n");}int main(){    int T;    scanf("%d",&T);    pri();    dfs(1,1,1);    for (int o=1;o<=T;o++)    {        printf("Case %d: ",o);        int type,k;        scanf("%d%d",&type,&k);        if (type) solve(k);        else solve1(k);    }    return 0;}

　　


联系
我们