LightOJ 1370 Bi-shoe and Phi-shoe(素数)

A - Bi-shoe and Phi-shoe
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit Status Practice LightOJ 1370 uDebug
Appoint description:

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,106].

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

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

题解：
这道题就是说给你n个数，对于这n个数依次 求某个数x的欧拉函数值不小于这个数的x最小值，将这n个数的最小值相加就是答案。
对于一个数的欧拉函数来说，其实并没有什么关系，我开始通过求欧拉函数，然后排序的做法，是不对的。

因为题目是求比至少比nums(nums为给的n个数的其中一个)大的欧拉函数值，然后这个欧拉函数值对应的数应该最小，比如a的欧拉函数值是b，我求出了b，反推a。

如果你觉得我上面这段话说的对，那么恭喜你，你理解的和我开始的理解一样，
错了 ^-^。

为什么呢，因为欧拉函数的值分布是没什么规律的，至少不是你这个数越大，欧拉函数值也越大。
比如phi(5)=1,但是phi(6)=3
附上欧拉函数的：
1 1
2 1
3 2
4 2
5 4
6 2
7 6
8 4
9 6
10 4
11 10
12 4
13 12
14 6
15 8

如果你想通过欧拉函数值反推原数，那么是行不通的，比如给你的数字是8，那么比8大的肯定推出来是15，但是事实上呢，是11。

所以我们必须抛弃这种方法。
不过我们可以发现欧拉函数值倒是有这样的规律，如果给你一个n，那么想求比n大的欧拉函数值，那么原数是肯定要比n大的，因为对于素数num,phi(num)=num-1。

那么我们筛素数，然后直接枚举上去就好了。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
const int inf=0x3f3f3f3f;

bool prime[maxn];

bool Judge(int now){
    int up=(int)sqrt(now*1.00);
    for(int i=2;i<=up;++i){
        if(now%i==0)return false;
    }
    return true;
}

int main() {
    for(int i=2; i<maxn; ++i) {
        prime[i]=Judge(i);
    }
    int T,Tc=0,n,nums;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        long long ans=0;
        for(int i=0; i<n; ++i) {
            scanf("%d",&nums);
            while(!prime[++nums]){}
            ans+=nums;
        }
        printf("Case %d: %lld Xukhan",++Tc,ans);
    }
    return 0;
}

（编辑：青岛站长网）

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