LightOJ-1370(欧拉函数)
发布时间:2020-12-14 05:09:40 所属栏目:大数据 来源:网络整理
导读:Bi-shoes and Phi-shoe LightOJ-1370 题目的含义含简单,就是先筛欧拉函数,打表,最后遍历就行了。 本题根据欧拉函数的特质还有一个不需要使用欧拉函数的方法,直接筛素数就行了。 另一种方法 #includeiostream#includecstring#includecstdio#includealgori
Bi-shoes and Phi-shoeLightOJ-1370
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxn=1e6+6; int a[10004]; int n; //欧拉函数表 int phi[maxn]; void phi_table(int n){ for(int i=2;i<=n;i++) phi[i]=0; phi[1]=1; for(int i=2;i<=n;i++){ if(!phi[i]){ for(int j=i;j<=n;j+=i){ if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } } } int main(){ phi_table(maxn); int t; cin>>t; int k=0; while(t--){ cin>>n; int x; long long ans=0; for(int i=0;i<n;i++){ cin>>x; for(int i=x+1;;i++){ if(phi[i]>=x){ ans+=i; break; } } } cout<<"Case "<<++k<<": "<<ans<<" Xukha"<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |