1. 首页
2. 数论
3. 本页

LightOJ 1370 Bi-shoe and Phi-shoe (欧拉函数)

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1050;

/*
int euler(int n){ //返回euler(n)
     int res=n,a=n;
     for(int i=2;i*i<=a;i++){
         if(a%i==0){
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出
             while(a%i==0) a/=i;
         }
     }
     if(a>1) res=res/a*(a-1);
     return res;
}
*/

//筛选法打欧拉函数表
#define Max 1000005
int euler[Max];
void Init()
{
     euler[1]=1;
     for(int i=2;i<Max;i++)
       euler[i]=i;
     for(int i=2;i<Max;i++)
        if(euler[i]==i)
           for(int j=i;j<Max;j+=i)
              euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
}

int a[10050];

int main()
{
    int t;
    cin>>t;
    Init();
    int casee=1;
    while(t--)
    {
        int n;
        cin>>n;
        LL sum=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        //cout<<sum<<endl;
        int tmp=2;
        for(int i=0;i<n;++i)
        {
            while(1)
            {
                if(euler[tmp]>=a[i])
                {
                    sum+=tmp;
                    break;
                }
                else
                tmp++;
            }
        }
        printf("Case %d: %lld Xukhan",casee++,sum);
       // cout<<sum<<endl;

    }

    return 0;
}