首页 > 代码库 > HDU4542 小明系列故事——未知剩余系
HDU4542 小明系列故事——未知剩余系
大赞的数论题;
大致思路:
对于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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。