Bi-shoe and Phi-shoe

题目

给出n个数字的序列a[]，对于每个数字ai找到一个欧拉函数值大于等于ai的数bi，求找到的所有数bi的最小值之和sum

分析

这是第二次写关于欧拉函数的题，这是使用了欧拉函数打表的模板，然后再处理一下最优值就可以了，其实也可以排序之后用二分。

需要处理的地方：

for(int i = 1;i<maxn;i++) mp[E[i]] = min(mp[E[i]],i)
这一句是将欧拉函数值E[i]一样的,取i较小的那个
for(int i = maxn-2;i>=1;i--) if(mp[i+1]) mp[i] = min(mp[i+1],mp[i])
这句是从后往前取最优值，比如mp[8] = 15,mp[9] = inf,mp[10] = 11
也就是欧拉值为8最小是15，欧拉值为9的没有(用的无穷大表示)，欧拉值为10最小是11，但是本题需要节省成本，所以需要mp[9] = min(mp[9],mp[10]) = 11,mp[8]=min(mp[8],mp[9]),所以mp[8] == mp[9] == mp[10] = 11,一个人的luckly值为8，9，10的时候选11长的杆子能节省成本。

AC代码

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
#include <stdio.h>
using namespace std;
const int maxn = 1101000;

int T,N;
int E[maxn],mp[maxn];
void init() //欧拉函数值打表，并求出题目中所有答案
{
    memset(mp,0x3f3f3f3f,sizeof mp);
    for(int i=2;i<maxn;i++){
        if(!E[i])
            for(int j=i;j<maxn;j+=i){
                if(!E[j]) E[j]=j;
                E[j] = E[j]/i*(i-1);
            }
    }
    for(int i = 1;i<maxn;i++) mp[E[i]] = min(mp[E[i]],i);
    for(int i = maxn-2;i>=1;i--){
        if(mp[i+1]) mp[i] = min(mp[i+1],mp[i]);
    }
}

int main(){
    init();
    int kase = 1;
    cin>>T;
    while(T--){
        scanf("%d",&N); int tmp;long long res = 0;
        for(int i = 1;i<=N;i++){
            scanf("%d",&tmp);
            res += mp[tmp];
        }
        printf("Case %d: %lld Xukha\n",kase++,res);
    }

    return 0;
}