HDU 4542 小明系列故事——未知剩余系（数论|反素数）

分析

kuangbin的blog已经讲的很好了，我做一点补充

1.当做x*y>z的比较时，如果x \(\ast\) y过大，可以写成x>z/y

2.分解质因数时选择用f[][0]保存质数，方便查错

3.写程序时分段写，防止变量名写错查很久

一道不错的题（对我来说）

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

const ll INF = 1LL<<62;

const int maxn = 1000;

int prime[maxn+10];

int p[maxn+10];

void get_prime()

{

    F(i,2,maxn)

    {

        if(!p[i]) prime[++prime[0]]=i;

        for(int j=1;j<=prime[0]&&prime[j]*i<=maxn;++j)

        {

            p[i*prime[j]]=1;

            if(i%prime[j]==0) break;

        }

    }

}

ll a[50050];

void dfs(ll num,int k,int sum,int limit)

{

    if(sum>47777) return ;

    if(a[sum]==0||a[sum]>num) a[sum]=num;

    for(int i=1;i<=limit;++i)

    {

        if(num>INF/prime[k]) break;

        num*=prime[k];

        if(num>INF) break;

        dfs(num,k+1,sum*(i+1),i);

    }

}

void init()

{

    mem(a,0);dfs(1,1,1,62);

}

int f[100][2];

ll calc(ll num)

{

    mem(f,0);

    int cnt=0;

    for(int i=1;prime[i]<=num/prime[i];++i) if(num%prime[i]==0)

    {

        f[++cnt][0]=prime[i];

        while(num%prime[i]==0) { f[cnt][1]++;num/=prime[i]; }

    }

    if(num!=1) f[++cnt][0]=num,f[cnt][1]=1;

    ll ans=1;

    F(i,1,cnt) ans*=(ll)(f[i][1]+1);

    return ans;

}

void solve(int k)

{

    for(ll x=2;x*x<=4*(x+k);++x)

    {

        if(x==calc(x+k)) { printf("%I64d\n",x+k );return; }

    }

    puts("Illegal");

}

int main()

{

    int t,type,k;

    get_prime();

    init();

    scanf("%d",&t);

    F(qq,1,t)

    {

        scanf("%d %d",&type,&k);

        printf("Case %d: ",qq );

        if(type==0)

        {

            if(a[k]==0) puts("INF");

            else printf("%I64d\n",a[k] );

        }

        else

        {

            solve(k);

        }

    }

    return 0;

}

巴特西

HDU 4542 小明系列故事——未知剩余系（数论|反素数）

最新文章

热门文章

巴特西

HDU 4542 小明系列故事——未知剩余系 （数论|反素数）

最新文章

热门文章

HDU 4542 小明系列故事——未知剩余系（数论|反素数）