Bi-shoe and Phi-shoe （欧拉函数）

题目描述：

题目大意：一个竹竿长度为p,它的score值就是比p长度小且与且与p互质的数字总数，比如9有1，2，4，5，7，8这六个数那它的score就是6。给你T组数据，每组n个学生，每个学生都有一个幸运数字，求出要求买n个竹子每个竹子的score都要大于或等于该学生的幸运数字，每个竹竿长度就是花费，求最小花费。

首先弄清欧拉函数的定义，详见：https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/1944850?fr=aladdin

函数内容

通式：

 

其中p1, p2……pn为x的所有质因数，x是不为0的整数。

φ(1)=1（和1互质的数(小于等于1)就是1本身）。

欧拉函数是积性函数——若m,n互质，

 

特殊性质：当n为质数时，

  

, 证明与上述类似。

若n为质数则

 

如：

ψ（10）=10×（1－1/2）×（1－1/5）=4；

ψ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8；

ψ（49）=49×（1－1/7）=  =42。 

利用欧拉函数和它本身不同质因数的关系，用筛选计算出某个范围内所有数的欧拉函数值。

/*
特性 :
1.若a为质数,phi[a]=a-1;
2.若a为质数,b mod a=0,phi[a*b]=phi[b]*a
3.若a,b互质,phi[a*b]=phi[a]*phi[b](当a为质数时,if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])
*/
int m[n],phi[n],p[n],nump;
//m[i]标记i是否为素数,0为素数,1不为素数;p是存放素数的数组;nump是当前素数个数;phi[i]为欧拉函数
int make()
{
        phi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!m[i])//i为素数
        {
            p[++nump]=i;//将i加入素数数组p中
            phi[i]=i-1;//因为i是素数,由特性得知
        }
        for (int j=1;j<=nump&&p[j]*i<n;j++)  //用当前已的到的素数数组p筛,筛去p[j]*i
        {
            m[p[j]*i]=1;//可以确定i*p[j]不是素数
            if (i%p[j]==0) //看p[j]是否是i的约数,因为素数p[j],等于判断i和p[j]是否互质
            {
                phi[p[j]*i]=phi[i]*p[j]; //特性2
                break;
            }
            else phi[p[j]*i]=phi[i]*(p[j]-1); //互质,特性3其,p[j]-1就是phi[p[j]]
        }
    }
}

现用另一种思路求任意一个数N，求出ψ（N），详见转载博客：https://blog.csdn.net/leolin_/article/details/6642096

代码实现：

 #include<stdio.h>     //欧拉之实现
 int ef(int n)
 {
     int cnt=n;
     int i;
     for(i=;i<=n;i++)
         if(n%i==)
         {
             cnt - =cnt/i;      //   m-m/p
             while(n%i==)
                 n/=i;
         }
         return cnt;
 }
 int main()
 {
     int n;int m;
     int count;
     while(scanf("%d",&m)!=EOF)
     {

         while(m--){
             scanf("%d",&n);
         count=ef(n);
         printf("%d\n",count);}
     }
     return ;
 }

看完上面的内容，我们就知道一根长度为p的竹竿它的score其实就是欧拉函数值φ(p)。又因为一个素数p的φ(p)=p-1，所以我们只需要从x+1(x是幸运数字)开始找第一个出现的素数，那就是最小花费。

代码实现：

 #include<iostream>
 using namespace std;
 typedef long long ll;
 const int N=1e7+;

 bool prime[N];

 void is_prime(){
     for(int i=;i<N;i++){
         prime[i]=true;
     }
     for(int i=;i*i<N;i++){
         if(prime[i]){
             for(int j=i*i;j<=N;j+=i){
                 prime[j]=false;
             }
         }
     }
 }

 int main(){
     is_prime();
     int t,n;
     cin>>t;
     for(int i=;i<=t;i++){
         cin>>n;
         ll sum=;
         for(int j=;j<=n;j++){
             int x;
             cin>>x;
             for(int k=x+;;k++){
                 if(prime[k]){
                     sum+=k;
                     break;
                 }
             }
         }
         cout<<"Case "<<i<<": "<<sum<<" Xukha"<<endl;
     }
 }