题解 B2134

admin2025-10-28 22:10:49【世界杯比赛赛】

题解 B2134

Dreamweaver

·

2021-07-17 19:34:13

·

题解

前言

这题算是“入门与面试”的题目里偏数学的一道，就来水一篇题解。

题意

两个质数的和是 S，它们的积最大是多少？

分析

根据基本不等式：

猜测应该是在 $S/2$ 两侧且最靠近 $S/2$ 的两个质数乘积最大。

证明如下：

设其中一组质数为 $a$ 和 $b$，另一组为 $a'$ 和 $b'$，且 $a'

$\because$ $a+b=S$，$a'+b'=S

\therefore$ $ans1=ab=a(S-a)=-a^2+Sa$，$ans2=a'b'=a'(S-a')=-a'^2+Sa'

由函数 y=-x^2+Sx 图像：

可得：对称轴为 x=S/2，函数在 [0,S/2] 上单调递增。

\because$ $a'

\therefore$ $-a'^2+Sa'<-a^2+Sa

\therefore$ $ans2

得证。

所以只要线性筛或埃氏筛或直接 O(\sqrt N) 判断，找出最靠近 S/2 的两个质数，输出其乘积即可。

代码

#include

using namespace std;

#define maxn 10010

#define re register

#define Orz cout<<"stO %王队% Orz"<'\n';

bool vis[maxn];

int pri[maxn],cnt,s;

void pre(int x)

{

vis[0]=vis[1]=true;

for(re int i=2;i<=x;++i)

{

if(!vis[i])

pri[++cnt]=i;

for(re int j=1;j<=cnt&&i*pri[j]<=x;++j)

{

vis[i*pri[j]]=true;

if(i%pri[j]==0) break;

}

}

}//线性筛

int main()

{

cin>>s;

pre(s+1);//线性筛预处理

for(re int i=s/2;i>=2;i--)

if(!vis[i]&&!vis[s-i]) //找到了

{

cout<

break;

}

return 0;

}