博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LightOJ 1370 Bi-shoe and Phi-shoe(欧拉函数)
阅读量:4839 次
发布时间:2019-06-11

本文共 852 字,大约阅读时间需要 2 分钟。

题意:

给一些数Ai(第 i 个数),Ai这些数代表的是某个数欧拉函数的值,我们要求出数 Ni 的欧拉函数值不小于Ai。而我们要求的就是这些 Ni 这些数字的和sum,而且我们想要sum最小,求出sum最小多少。

 

思路:

素数P的欧拉函数值为P-1。

所以对于一个给出的数,我们去寻找大于它的第一个素数即可。

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 using namespace std;11 12 const int maxn=1e6+5;13 14 int n;15 int vis[maxn];16 17 void get_primes()18 {19 int m=sqrt(maxn+0.5);20 for(int i=2;i<=m;i++)21 {22 if(!vis[i])23 {24 for(int j=i*i;j<=maxn;j+=i)25 vis[j]=1;26 }27 }28 }29 30 int main()31 {32 //freopen("D:\\input.txt","r",stdin);33 int T;34 int kase=0;35 get_primes();36 scanf("%d",&T);37 while(T--)38 {39 long long sum=0;40 scanf("%d",&n);41 for(int i=0;i

 

转载于:https://www.cnblogs.com/zyb993963526/p/6819446.html

你可能感兴趣的文章
结对2.03
查看>>
【vue】vue如何创建一个项目
查看>>
简单的linux压力测试工具webbench
查看>>
ImageLunBo_shape+XML
查看>>
php实现设计模式————单例模式
查看>>
Python OOP(面向对象编程)
查看>>
MySQL安装与测试
查看>>
使用JDK自带的VisualVM进行Java程序的性能分析
查看>>
mysql语句记录
查看>>
总结面试题
查看>>
Win8AX博客园应用隐私声明
查看>>
windows中的软链接硬链接等
查看>>
如何在本地调试微信接口
查看>>
Java二分法
查看>>
杭电acm2099
查看>>
Linux GCC常用命令
查看>>
拷贝变换3字节像素到4字节内存
查看>>
PythonDay01
查看>>
Oracle数据库的JDBC衔接
查看>>
运用 KCheckGmail 监视 Gmail
查看>>