Bamboo Pole-vault is a massively popular sport in Xzhiland. And Master Phi-shoe is a very popular coach for his success. He needs some bamboos for his students,so he asked his assistant Bi-Shoe to go to the market and buy them. Plenty of Bamboos of all possible integer lengths (yes!) are available in the market. According to Xzhila tradition,

Score of a bamboo =?Φ (bamboo's length)

(Xzhilans are really fond of number theory). For your information,?Φ (n)?= numbers less than?n?which are relatively prime (having no common divisor other than 1) to?n. So,score of a bamboo of length 9 is 6 as 1,2,4,5,7,8 are relatively prime to 9.

The assistant Bi-shoe has to buy one bamboo for each student. As a twist,each pole-vault student of Phi-shoe has a lucky number. Bi-shoe wants to buy bamboos such that each of them gets a bamboo with a score greater than or equal to his/her lucky number. Bi-shoe wants to minimize the total amount of money spent for buying the bamboos. One unit of bamboo costs 1 Xukha. Help him.

Input

Input starts with an integer?T (≤ 100),denoting the number of test cases.

Each case starts with a line containing an integer?n (1 ≤ n ≤ 10000)?denoting the number of students of Phi-shoe. The next line contains?n?space separated integers denoting the lucky numbers for the students. Each lucky number will lie in the range?[1,10⁶].

Output

For each case,print the case number and the minimum possible money spent for buying the bamboos. See the samples for details.

?

给一些数，这些数代表的是某个数欧拉函数的值，求出数 Ni 的欧拉函数值不小于Ai。最终求的是这些 Ni?这些数字的和ans最小值。

题解：

要求和最小，我们可以让每个数都尽量小，那么我们最后得到的肯定就是一个最小值。

给定一个数的欧拉函数值ψ(N)(就是题目里的a[i])，我们怎么样才能求得最小的N?

我们知道，一个素数P的欧拉函数值ψ(P)=P-1。所以如果我们知道ψ(N)，那么最小的N就是大于ψ(N)的最小素数。

最后：打 表判断即可

#include<cstdio>
int su[1000100]={1,1};
int main()
{
	for(int i=2;i<=500000;i++)
	{
		if(su[i])
			continue;
		for(int j=i+i;j<=1000010;j+=i)
			su[j]=1;
	}
	int u,n;
	long long ans;
	int ca=1;
	scanf("%d",&u);
	while(u--)
	{
		scanf("%d",&n);	
		ans=0;
		while(n--)
		{		
			int t;
			scanf("%d",&t);
			for(int i=t+1;;i++)
			{
				if(!su[i])
				{
					ans+=i;
					break;
				}
			}
		}
		printf("Case %d: %lld Xukhan",ca++,ans);
	}
	return 0;
 } 

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!