[kuangbin带你飞]专题十四数论基础 A - Bi-shoe and Phi-shoe LightOJ - 1370(欧拉值）

Myth丶恋晨 2023-08-17 15:41 61阅读 0赞

# A - Bi-shoe and Phi-shoe LightOJ - 1370 #

题目链接[：https://vjudge.net/contest/70017\#problem/A][https_vjudge.net_contest_70017_problem_A]

## 题目： ##

Bamboo Pole-vault是Xzhiland的一项大受欢迎的运动。 Phi-shoe大师是他成功的非常受欢迎的教练。他需要为他的学生提供一些竹子，所以他让他的助手Bi-Shoe去市场购买。市场上有很多可能的整数长度的Bamboos（是的！）。根据Xzhila的传统，  
  
    竹子的分数=Φ（竹子的长度）  
  
    （Xzhilans非常喜欢数论）。对于您的信息，Φ（n）=小于n的数字，它们相对于素数（除了1之外没有公约数）到n。因此，长度为9的竹子的得分为6，因为1,2,4,5,7,8是9的相对素数。  
  
    助理双鞋必须为每个学生买一个竹子。作为一个扭曲，Phi-shoe的每个撑杆跳学生都有一个幸运数字。 Bi-shoe希望购买竹子，这样他们每个人都会得到一张分数大于或等于他/她的幸运数字的竹子。 Bi-shoe希望最大限度地减少购买竹子所花费的总金额。一个竹子单位花费1 Xukha。帮助他  
输入  
  
    输入以整数T（≤100）开始，表示测试用例的数量。  
  
    每个案例都以包含整数n（1≤n≤10000）的行开头，表示Phi-shoe的学生人数。下一行包含n个空格分隔的整数，表示学生的幸运数字。每个幸运数字将位于\[1,106\]范围内。  
产量  
  
    对于每种情况，打印案例编号和购买竹子所花费的最少金额。有关详细信息，请参阅示例

Sample Input

1 2 3 4 5

10 11 12 13 14 15

1 1

Sample Output

Case 1: 22 Xukha

Case 2: 88 Xukha

Case 3: 4 Xukha

## **思路：** ##

**这题竹子的分数就是n的欧拉值（即少于或等于n的数中与n互质的数的数目），且如果n是素数的话，他的欧拉值为n-1，**

**这里要求这样的一个数要使得该数的欧拉值大于该人的幸运数字，求得所有人对应的这些数（该数的欧拉值大于幸运数字）的最小值**

**<<**

**附：欧拉函数的几个性质如下：**

**所以说φ（mn）=φ（m）\*φ（n）只有在（m，n）=1时成立（通俗来说就是m，n互质啦）；  
  
2.除了N=2，φ（N）都是偶数；  
  
3.当N为奇数时，φ（2\*N）=φ（N）；  
  
4.若N是质数p的k次幂，φ（N）=p^k-p^(k-1)=(p-1)p^(k-1) 因为除了p的倍数之外，其他数都与N互质；  
  
5.当N是质数时，φ（N）=N-1；**

**>>**

//
    // Created by hanyu on 2019/8/9.
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int maxn=3e6+7;
    #define MAX 0x3f3f3f3f
    int euler[maxn];
    void value()
    {
        memset(euler,0,sizeof(euler));
        euler[1]=1;
        for(int i=2;i<=maxn;i++)
        {
            if(!euler[i])
            {
                for(int j=i;j<=maxn;j+=i)//这里是j+=i,不是j++
                {
                    if(!euler[j])
                        euler[j]=j;
                    euler[j]=euler[j]/i*(i-1);
                }
            }
        }
    }
    int main()
    {
        int pos=0;
        int n,t;
        value();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            ll sum=0;
            for(int i=0;i<n;i++)
            {
                int a;
                scanf("%d",&a);
                for(int j=a+1;j<=maxn;j++)
                {
                    if(euler[j]>=a)
                    {
                        sum+=j;
                        break;
                    }
                }
            }
            printf("Case %d: %lld Xukhan\n",++pos,sum);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11326864.html

[https_vjudge.net_contest_70017_problem_A]: https://vjudge.net/contest/70017#problem/A