首页 > 其他 > 详细

light1370 欧拉函数打表

时间:2019-02-14 20:58:27      阅读:302      评论:0      收藏:0      [点我收藏+]
/*
给定n个数ai,要求欧拉函数值大于ai的最小的数bi
求sum{bi} 
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
int n,a[maxn];

int phi[maxn],m,v[maxn],prime[maxn];
void init(int n){
    memset(v,0,sizeof v);
    m=0;
    for(int i=2;i<n;i++){
        if(v[i]==0){//i是质数 
            v[i]=i,prime[++m]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=m;j++){ 
            if(prime[j]>v[i] || prime[j]*i>n)break; 
            v[i*prime[j]]=prime[j];//筛素数
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:
                                               prime[j]); 
        } 
    }
}
/*int phi[maxn];
void init(int n){//用era筛的思路O(nlogn)复杂度 
    phi[1]=1;
    for(int i=2;i<=n;i++)phi[i]=i;
    for(int i=2;i<=n;i++)
        if(phi[i]==i)//i是质数
            for(int j=1;i*j<=n;j++)
                phi[i*j]=phi[i*j]/i*(i-1); 
}*/
int main(){
    int t,tt;
    init(maxn);
    cin>>t;
    for(tt=1;tt<=t;tt++){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+1+n);
        
        int j=1;
        long long ans=0;
        for(int i=2;i<maxn;i++){
            while(phi[i]>=a[j] && j<=n)
                ans+=i,j++;
        }
        printf("Case %d: %lld Xukha\n",tt,ans);
    }
} 

 

light1370 欧拉函数打表

原文:https://www.cnblogs.com/zsben991126/p/10380640.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!