(lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)

Topic link ：Bi-shoe and Phi-shoe - LightOJ 1370 - Virtual Judge

give n A sequence of numbers a[], For each number ai Find an Euler function whose value is greater than or equal to ai Number of numbers bi, Find all the numbers found bi The sum of the minimum values of sum（ Euler function is specified here 1 The value of is 0）

Input

Yes T（T<=100） Group data , Each set of data has two lines , The first line gives n（n<=10000） The second line gives the length n Sequence a[],ai The value range of is [1,1000000]

Output

Output a number sum

Sample Input

3

5

1 2 3 4 5

6

10 11 12 13 14 15

2

1 1

Sample Output

Case 1: 22 Xukha

Case 2: 88 Xukha

Case 3: 4 Xukha

analysis ： This problem is to examine the Euler function and make a table , If you don't know this, you can check my previous blog , It introduces in detail the principle of Euler function table , Here is the blog address ： Euler function method and its basic application _AC__dream The blog of -CSDN Blog _ Euler function method

  When we find the Euler function of all numbers , We can directly check the table , Here we can use a greedy thought , First of all, we can know from the definition of Euler function , The Euler function value is greater than x The number of must be greater than x, So every time we look up the first Euler function, the value is greater than a[i] The number of hours can be from a[i] Start looking up the table , Before checking the table, we can check a Array to sort , This will play an optimization role to a certain extent , Then check the table in an increasing order , Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1000005;// There must be an Euler function greater than 1000000 Number of numbers , Including prime numbers 1000003 that will do  
bool vis[N];
int prime[N],o[N],cnt,a[N];
void init()
{
	o[1]=0;// Default in this question 1 The Euler function of is 0 
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			prime[++cnt]=i;
			o[i]=i-1;
		}
		for(int j=1;j<=cnt&&i*prime[j]<N;j++)
		{
			vis[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				o[i*prime[j]]=o[i]*prime[j];
				break;
			}
			else
				o[i*prime[j]]=o[i]*(prime[j]-1);
		}
	}
}
int main()
{
	init();
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		int pos=a[1];
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			while(o[pos]<a[i]) pos++;
			ans+=pos;
		}
		printf("Case %d: %lld Xukha\n",_,ans);
	}
	return 0;
}