BNU 13288 Bi-shoe and Phi-shoe(欧拉函数)
发布时间:2020-12-14 02:44:00 所属栏目:大数据 来源:网络整理
导读:大概题意是定义Φ(n)是小于n并且与n互质的数字个数,也就是欧拉函数...然后给定n个Φ (x),找出来n个x使得n个x的和最小... 因为是刚接触数论...刚开始想着会不会有非素数被选中呢...然后如果带有非素数被选中的话复杂度很高...后来考虑是不是对于某个x,只
大概题意是定义Φ(n)是小于n并且与n互质的数字个数,也就是欧拉函数...然后给定n个Φ (x),找出来n个x使得n个x的和最小... 因为是刚接触数论...刚开始想着会不会有非素数被选中呢...然后如果带有非素数被选中的话复杂度很高...后来考虑是不是对于某个x,只要找到比x大的最小素数就是这个x对应的答案呢...数学渣只能举例子了...比如Φ (7)=6,Φ (11)=10,那么6到10之间的数字应该怎么确定...选择非素数么?对于欧拉值是7来说,x肯定是大于11的不如直接选择11...so,答案就出来了... 筛选法求欧拉函数值对应的x,对于输入带入即可
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; #define N 1010000 int num[N+20],prime[N+20]; int p[N+20]; void euler() { int k=0; memset(num,sizeof(num)); for(int i=2;i<=N;i++) { if(!num[i]) { prime[k++]=i; for(int j=i+i;j<=N;j+=i) num[j]=1; } } int t=0; for(int i=1;i<=N;i++) { while(i>=prime[t]) t++; p[i]=prime[t]; } } int main() { euler(); int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { long long ans=0; int n,a; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a); ans+=p[a]; } printf("Case %d: %lld Xukhan",cas,ans); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |