LightOJ - 1370

Time Limit: 2000MS

Memory Limit: 32768KB

64bit IO Format: %lld & %llu

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

Source

Problem Setter: Mir Wasi Ahmed

Special Thanks: F.A. Rezaur Rahman Chowdhury, Jane Alam Jan

/**

          题意：f(n) 表示 小于等于 n 的数中素数的个数；给出一串数 比如x 求f(x) >= x 的最小和

          做法：欧拉函数

**/

#include <iostream>

#include<cmath>

#include<string.h>

#include<stdio.h>

#include<algorithm>

#include<stack>

#define maxn 1000000 + 10

int mindiv[maxn],phi[maxn],sum[maxn];

int mmap[maxn];

int mmpp[maxn];

using namespace std;

void solve()

{

    for(int i=; i<maxn; i++)

    {

        mindiv[i] = i;

    }

    for(int i=; i*i<maxn; i++)

    {

        if(mindiv[i] == i)

        {

            for(int j=i*i; j<maxn; j+=i)

            {

                mindiv[j] = i;

            }

        }

    }

    phi[] = ;

    for(int i=; i<maxn; i++)

    {

        phi[i] = phi[i/mindiv[i]];

        if((i/mindiv[i])%mindiv[i] == )

        {

            phi[i] *=mindiv[i];

        }

        else

        {

            phi[i] *= mindiv[i] -;

        }

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif // ONLINE_JUDGE

          int T;

          scanf("%d",&T);

    int n;

    solve();

    int Case = ;

    while(T--)

    {

                    scanf("%d",&n);

        int res = ;

        long long sum = ;

        for(int i=; i<n; i++)

        {

            scanf("%d",&mmpp[i]);

        }

        sort(mmpp,mmpp+n);

        int tt=  ,Index = ;

        int j = ;

        phi[] = ;

        for(int i=; i<n; )

        {

            if(phi[j] >= mmpp[i])

            {

                sum += j;

                i++;

            }

            else j++;

        }

        printf("Case %d: %lld Xukha\n",Case++,sum);

    }

    return ;

}

巴特西

LightOJ - 1370

最新文章

热门文章