集训Day 3

王浩泽 / 2023-07-27 / 原文

A题：

B题：

比赛开始，直接跟着A题的样例开搞，成功拿下题目（get100pt），B题我写了一个肯定会爆的桶，后来为了多拿分就将数组开大了亿点然后就炸了痛失了B题15pt以及前三。（哭）

改题的时候依旧不严谨，B题订正时脑袋里想的是if else 的写法实际写的是 if判断后未加return 0导致输出重复的做法。

不严谨了两天了，第一天因为提交前没重新运行一遍挂了一次，今天又来了一次。

B题题解：

首先，当n=1答案一定为1e9。（在程序开头做特判即可）

再来仔细阅读题目即可发实擦去之后填入新的只是一个幌子，本质上是在要求你擦掉一个数字之后其他所有数的最大公因数。那么我们就可以写出偏向暴力的程序，但为了追求更好，我们此时可以发现就是在数组内选一个点使得其左右两边的所有数公共因数最大，那么接下来我们可以发现我们可以通过前、后缀和来优化暴力中的求余下的数的gcd就可以得到正解。

B题代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],p[N],s[N];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
} 
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    if(n==1)
    {
        cout<<"1000000000";
        return 0; 
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) p[i]=gcd(a[i],p[i-1]);
    for(int i=n;i;i--) s[i]=gcd(a[i],s[i+1]);
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,gcd(p[i-1],s[i+1]));
    cout<<ans;
    return 0;
}

A题代码：

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d;
int main()
{
    ios::sync_with_stdio(false);
    cin>>a>>b>>c>>d;
    long long t2=a*c,t3=a*d,t4=b*c,t5=b*d;
    cout<<max(max(t2,max(t2,max(t3,t4))),max(t5,t2));
    return 0;
}