首页 > 代码库 > HDU4542 小明系列故事——未知剩余系
HDU4542 小明系列故事——未知剩余系
题意:给一系列操作,每个操作有两个数t和k,t=0表示求k以内的最大反素数;t=1表示求小于k且与k互质的数的个数。
分析:对第一个操作,直接用dfs求反素数就行了,直接上反素数的模板;第二个操作素数筛法的思想预先打个表。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<set> #include<map> #include<queue> #define maxn 60001 #define inf (1ll<<62) using namespace std; long long _,type,k,np[maxn],ans,ca=0; int p[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; void dfs(int kk,long long num,long long sum,long long limit) { if (sum>k) return ; if (sum==k) ans=min(ans,num); for (int i=1;i<=limit;i++) { if (ans/p[kk] <num || sum*(i+1)>k) break; num*=p[kk]; if (k%(sum*(i+1))==0) dfs(kk+1,num,sum*(i+1),i); } } int main() { scanf("%lld",&_); int i,j; for (i=0;i<maxn;i++) np[i]=i; for (i=1;i<maxn;i++) { for (j=i;j<maxn;j+=i) np[j]--; if (!np[np[i]]) np[np[i]]=i; np[i]=0; } //for (i=1;i<=100;i++) cout<<np[i]<<endl; while (_--) { scanf("%lld%lld",&type,&k); if (type==1) ans=np[k]; else { ans=inf; dfs(0,1,1,62); } printf("Case %lld: ",++ca); if (ans==0) puts("Illegal"); else if (ans>=inf) puts("INF"); else printf("%lld\n",ans); } return 0; }
HDU4542 小明系列故事——未知剩余系
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。