题目描述：

 

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

首先弄清欧拉函数的定义，详见：

函数内容

通式：

 

其中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]*a3.若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，求出ψ（N），详见转载博客：

代码实现：

1 #include
     
           //欧拉之实现 2 int ef(int n) 3 { 4     int cnt=n; 5     int i; 6     for(i=2;i<=n;i++) 7         if(n%i==0) 8         { 9             cnt - =cnt/i;      //   m-m/p10             while(n%i==0)11                 n/=i;12         }13         return cnt;14 }15 int main()16 {17     int n;int m;18     int count;19     while(scanf("%d",&m)!=EOF)20     {21         22         while(m--){23             scanf("%d",&n);24         count=ef(n);25         printf("%d\n",count);}26     }27     return 0;28 }
     

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

代码实现：

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int N=1e7+5; 5  6 bool prime[N]; 7  8 void is_prime(){ 9     for(int i=2;i
      
       >t;25     for(int i=1;i<=t;i++){26         cin>>n;27         ll sum=0;28         for(int j=1;j<=n;j++){29             int x;30             cin>>x;31             for(int k=x+1;;k++){32                 if(prime[k]){33                     sum+=k;34                     break;35                 }36             }37         }38         cout<<"Case "<
       <<": "<
        
         <<" Xukha"<