【LightOJ - 1370】Bi-shoe and Phi-shoe

2019/7/21 16:52:13 人评论 次浏览 分类:学习教程

Bi-shoe and Phi-shoe

Descriptions:

给出一些数字,对于每个数字找到一个欧拉函数值大于等于这个数的数,求找到的所有数的最小和。

Input

输入以整数T(≤100)开始,表示测试用例的数量。

每个案例都以一行包含整数n(1≤n≤10000)开始,表示有n个数。下一行包含n个空格分隔的整数,表示数字。每个数字都在[1,10^6]范围内。

Output

求找到的所有数的最小和

Sample Input

3

5

1 2 3 4 5

6

10 11 12 13 14 15

2

1 1

Sample Output

Case 1: 22 Xukha

Case 2: 88 Xukha

Case 3: 4 Xukha

题目链接

https://vjudge.net/problem/LightOJ-1370

先欧拉函数打表,再一一对照着找表即可

#include  #include  #include  #include  #include  #include  #include  #include  #include <string> #include  #include  #include  #include <set> #include  #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 1100000 using namespace std; int T,n; int phi[Maxn+1];//存欧拉函数 bool isPrime[Maxn+1];//存素数 int a[Maxn]; void Eular()//求欧拉函数 {     for(int i=1;i<=Maxn;i++) phi[i]=i;     memset(isPrime,true,sizeof(isPrime));     isPrime[0]=isPrime[1]=false;     phi[1]=0;     for(int i=2;i<=Maxn;i++)     {         if(isPrime[i])         {             for(int j=i;j<=Maxn;j+=i)             {                 isPrime[j]=false;                 phi[j] -= phi[j]/i;             }         }     } } int main() {     int Case=0;     Eular();//打表     cin>>T;     while(T--)     {         MEM(a,0);         cin>>n;         for(int i=0;i)             cin>>a[i];         ll sum=0;         sort(a,a+n);         int pos=1;         for(int i=0;i)         {             for(int j=pos;j)             {                 if(phi[j]>=a[i])                 {                     sum+=j;                     pos=j;                     break;                 }             }         }         printf("Case %d: %lld Xukha\n",++Case,sum);     } }

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->