【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

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

题目链接

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);     } }

本文链接: http://www.luyixian.cn/news_show_103106.aspx 分享到：腾讯新浪人人网邮件收藏夹复制网址更多

上一篇：第0篇CSDN文章

下一篇：office2019激活码激活秘钥

推荐资源

打卡神器

学习教程

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

Bi-shoe and Phi-shoe

相关资讯

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

推荐资源

打卡神器

学习教程

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

Bi-shoe and Phi-shoe

相关资讯

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

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