LightOJ1370-Bi-shoe and Phi-shoe 【欧拉函数】

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;
}
全部评论

相关推荐

Java抽象带篮子:难蚌,点进图片上面就是我的大头😆
点赞 评论 收藏
分享
11-08 13:58
门头沟学院 Java
程序员小白条:竟然是蓝桥杯人才doge,还要花钱申领的offer,这么好的公司哪里去找
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务