P8219 [WFOI - 02] I wanna a feasitor（化验器） 题解

FFTotoro · 2022-03-22 19:46:17 · 题解

分析题目后我们可以发现，一个数的最大因数会等于这个数除以除 1 外的最小因数。

所以，一个数的最小因数（除 1 外）越小，它的最大因数就越大；因数最小只可能是 2。

综上所述，如果 r 是偶数，那么这个区间内的最大的 f(x) 就是 \frac{r}{2}；否则最大值为 \frac{r-1}{2}。即答案为 \left\lfloor\frac{r}{2}\right\rfloor。

放代码：

#include<iostream>
using namespace std;
int main(){
  long long l,r; cin>>l>>r;
  cout<<(r>>1)<<endl;
  return 0;
}