LightOJ 1370 Bi-shoe and Phi-shoe 欧拉函数

1. 相邻两个素数的欧拉函数值是区间内的最大值。

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

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<vector>
#include<fstream>
#include<list>
using namespace std;

#define ms(s) memset(s,sizeof(s))
typedef unsigned long long ULL;
typedef long long LL;

const int INF = 0x3fffffff;

const int N = 1001000;
bool primeTable[N+5];
int p[N+5];

void make_primeTable(){
    fill(primeTable,primeTable+N,1);
    primeTable[0] = false;
    primeTable[1] = false;

    int maxed = sqrt(N);
    for(int i = 2; i <= maxed; ++i){
        if(primeTable[i]){
            for(int j = i*i; j <= N; j += i)
                primeTable[j] = false;
        }
    }
}

int main()
{
// freopen("F:input.txt","r",stdin);
// freopen("F:output.txt","w",stdout);
// ios::sync_with_stdio(false);

    make_primeTable();

    int k = 1000003;
    for (int i = 1000000; i >= 1; --i) {
        if (primeTable[i] == true) {
            p[i] = k;
            k = i;
            continue;
        }
        p[i] = k;
    }

    int t,n,l;
    int j = 1;
    long long ans;
    scanf("%d",&t);
    while(j <= t){
        ans = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; ++i){
            scanf("%d",&l);
            ans += p[l];
        }
        printf("Case %d: %lld Xukhan",j,ans);
        j++;
    }




    return 0;
}