【刷题记录】 LightOJ-1370 Bi-shoe and Phi-shoe 数论+素数_lightoj1370

目录

一. 问题描述

二. 题解代码

一. 问题描述

Problem Description

已知每个长度为L的竹子，其分数p(L) = 其1~L中与其互素的元素个数，也就是欧拉函数。

现在给出一系列n个学生的期望值，要求求出分数>=每个学生期望值的竹子最短长度的和。

也就是在满足竹子sorce>=A[i]&&竹子L最小。

二. 题解代码

已知：素数X的欧拉函数 = X - 1；

我们可以举例写出一些数字的欧拉函数来：

数字：1 2 3 4 5 6 7 8 9 10 11

欧拉：1 1 2 2 4 2 6 4 6 4  10

        由上我们发现：两个素数之间的数字的欧拉值介于两素数欧拉值之间，也就是每个素数为一个跃点。现在给你一个数字n，让n成为欧拉值，n一定位于两素数之间，那么：

（1）如果n+1是一个素数，那么（n+1）就是最小长度，其欧拉值为n；

（2）否则就找第一个>=(n+1)的素数p，其欧拉值为p-1，也一定为最优；

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 7;
bool vis[maxn];
int prime[maxn],tot,Arr[10007];
typedef long long LL;
void init(){
   tot = 0;
   memset(vis,0,sizeof(vis));
   vis[1] = 1;
   for(int i = 2;i<maxn;i++){
      if(!vis[i])prime[tot++] = i;
      for(int j = 0;j<tot;j++){
         if(i*prime[j]>=maxn)break;
         vis[i*prime[j]] = 1;
         if(i%prime[j]==0)break;
      }
   }
}
int main()
{
    int T;
    scanf("%d",&T);
    int t = 0;
    init();
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i = 0;i<n;i++){
            scanf("%d",&Arr[i]);
        }
        LL sum = 0;
        for(int i = 0;i<n;i++){
            int pos =lower_bound(prime,prime+tot,Arr[i]+1) - prime;
            sum+=prime[pos];
        }
        printf("Case %d: %lld Xukha\n",++t,sum);
    }
    return 0;
}