牛牛做数论＜每日一题分享＞

题目：

做题思路：

做这题我们首先要了解什么是欧拉函数

---

欧拉函数：
就是对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。

欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)

其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

---

那么题目所给的H(x)表达式为H(x)=(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn).

其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

所以题目转换成求

2到n的满足条件1最小的一个值

和

2到n的满足条件1最大的一个值

由H(x)函数求的为从2到n的所有的（1-1/p）的乘【p为所有不同的质因子】

那么我们可以轻易的推出

要使H(x)最小

那么我们只需满足使n所有不同的质因子（1-1/p）相乘

要使H(x)最大

那么我们就要找到

从n一直向下的最大的素数

 下面的图片可以帮助大家理解为什么会这样：

 故我们可以写出代码详解：

#include#includeusing namespace std;typedef long long ll;#includeint su[10] = { 0,2,3,5,7,11,13,17,19,23 };//取从2乘到23就已经可以取到所有的nbool sushu(int n)//判断素数{ if(n==2||n==3) return 1; if(n%6!=5&&n%6!=1) return 0; for(int i=5;i*i<=n;i+=6) { if(n%i==0||n%(i+2)==0) return 0; } return 1;}int main(){int t;cin >> t;int n;while (t--){int ans1 = 1, tmb = 3;scanf("%d", &n);ll ans2 = n;if (n == 1)//特殊情况特判{cout << -1 << endl;continue;}for (int i = 1; i <= 9; i++)//找到小于n的最大能够取的乘积{if (su[i] * ans1 <= n) ans1 *= su[i];else break;}while (1)//从n递减，找到2到n的最大素数{if (sushu(ans2)) break;ans2--;}cout << ans1 << " " << ans2 << endl;}return 0;}

 PS:新年快乐啊各位大佬。新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐新年快乐