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;
}
优质内容筛选与推荐>>
1、软考--数据通信与网络基础
2、mysql导入导出表中含有longblob类型字段的数据
3、记录linux /bin被误删除的解决过程
4、HDU 1257 最少拦截系统(贪心)
5、RedGate 工具SQLMultiScript1.1


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号