LightOj 1370 Bi-shoe and Phi-shoe

发布时间：2020-12-14 02:18:01 所属栏目：大数据来源：网络整理

导读：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70017#problem/A Bi-shoe and Phi-shoe Description 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 b

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70017#problem/A

Bi-shoe and Phi-shoe

Description

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.

Sample Input

1 2 3 4 5

10 11 12 13 14 15

1 1

Sample Output

Case 1: 22 Xukha

Case 2: 88 Xukha

Case 3: 4 Xukha

题目大意：首先你需要明白欧拉函数是什么：欧拉函数指的是n以内与n互质的所有数的个数。

假如n是质数，很明显，它的欧拉函数等于n-1；

题目给你n个x，然后你要求出n个数的和，这n个数对应的欧拉函数大于x

反正总结一句话就是 ??欧拉函数大于等于x的那个数就是x+1之后的第一个质数

高效素数打表

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <queue>
#include <stack>
#include <vector>
#include <map>


using namespace std;


#define N 1500000
#define INF 0x3f3f3f3f
#define PI acos (-1.0)
#define EPS 1e-8
#define met(a,b) memset (a,b,sizeof (a))


int prime[N] = {1,1,0};


void Isprime ()
{
    for (int i=2; i<=N; i++)
    {
        if (!prime[i])
        {
            for (int j=i+i; j<=N; j+=i)
                prime[j] = 1;
        }
    }
}


int main ()
{
    int t,k = 1,n;
    scanf ("%d",&t);


    Isprime ();


    while (t--)
    {
        scanf ("%d",&n);
        long long sum = 0,x;


        for (int i=1; i<=n; i++)
        {
            scanf ("%lld",&x);
            for (int j=x+1; ; j++)
                if (!prime[j])
                {
                    sum += j;
                    break;
                }
        }
        printf ("Case %lld: %lld Xukhan",k++,sum);
    }
    return 0;
}

（编辑：李大同）

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