专栏首页一Wa哇一天HPU第一次积分赛 E.Max Gcd

HPU第一次积分赛 E.Max Gcd

E. Max Gcd

单点时限: 2.0 sec 内存限制: 512 MB

一个数组a,现在你需要删除某一项使得它们的gcd最大,求出这个最大值。

输入格式 第一行输入一个正整数n,表示数组的大小,接下来一行n个数,第i个数为ai。(2≤n≤105,1≤ai≤109)

输出格式 输出删除掉某个数以后的gcd的最大值。

样例

input 4 2 4 8 1 outpu| 2

input 4 1 2 3 4

output 1

提示 样例一:删除第四个元素后,2,4,8的最大公因子为2。 样例二:无论删除哪一个,最大公因子都为1。

这个题刚开始想着直接暴力,后来发现时间不允许就放弃了,赛后我是师父说直接先把数组从前到后依次gcd存在一个数组里,然后在从后向前依次gcd再放另一个数组里,然后在直接暴力就行了!

红线代表从前向后依次gcd,蓝线是从后向前。然后一个一个去除保留最大的数据就行!

#include<algorithm>
#include<iostream>

using namespace std;

int a[100100],b[100100],c[100100];

int main()
{
    int n;
    cin>>n;
    cin>>a[1];
    b[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        cin>>a[i];
        b[i]=__gcd(b[i-1],a[i]);//从前向后依次gcd
    }
    c[n]=a[n];
    for(int i=n-1;i>=1;i--)
    {
        c[i]=__gcd(c[i+1],a[i]);//从后向前依次gcd
    }
    int maxn=max(b[n-1],c[2]);//因为防止数组下标越界所以事先比较去掉第一项和
                            //去掉最后一项哪个大,保留打的一个
    for(int i=2;i<n;i++)
    {
//b[i-1]和c[i+1]刚好是第i项之前的所有项的gcd和第i项之后的所有项的gcd    
        maxn=max(__gcd(b[i-1],c[i+1]),maxn);
        //因为一直保留的是最大的值,所以最后的maxn就是答案
    }
    cout<<maxn<<endl;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • D. Same GCDs

    time limit per test:2 seconds memory limit per test:256 megabytes inputstandard...

    某些人
  • 并查集

    POJ 的题真的是对小白选手的一个大的磨炼了,看了好久才明白题意,然后发现还是不会写题意就是给你一个数n,然后又n次操作,每次操作有两种情况如果第一个字符是 M...

    某些人
  • CF-1197C-C. Array Splitting

    某些人
  • codeforces 1349A(数学)

    题意要求求出gcd(lcm(a_{i},a_{j})) | i<j,由于lcm(a_{i},a_{j})=a_{i}*a_{j}/gcd(a_{i},a_{j}...

    dejavu1zz
  • 扩展欧几里德算法

    对于不完全为 0 的非负整数 a,b,若gcd(a,b)表示 a,b 的最大公约数,必然存在整数对x,y ,使得 ax+by = gcd(a,b)。

    饶文津
  • 对于注册中心,ZooKeeper、Eureka 哪个更合适?

    Eureka本身是Netflix开源的一款提供服务注册和发现的产品,并且提供了相应的Java封装。在它的实现中,节点之间相互平等,部分注册中心的节点挂掉也不会对...

    芋道源码
  • Unity-黑暗之魂复刻-角色攻击

    1.在原来的BaseLayer基础上,新增加LayerMask,Weight表示新增层的权重,Blending我们设置成override。 2.创建avata...

    祝你万事顺利
  • WebAssembly试玩

    主要目标是在Web环境支持高性能应用。但设计上不依赖Web特性,也不针对Web特性提供功能,也可以用在其它环境

    ayqy贾杰
  • Nginx fastcgi_cache权威指南

    Nginx版本从0.7.48开始,支持了类似Squid的缓存功能。这个缓存是把URL及相关组合当做Key,用Md5算法对Key进行哈希,得到硬盘上对应的哈希目录...

    sunsky
  • 2019 前端面试题汇总(主要为 Vue)

    毕业之后就在一直合肥小公司工作,没有老司机、没有技术氛围,在技术的道路上我只能独自摸索。老板也只会画饼充饥,前途一片迷茫看不到任何希望。于是乎,我果断辞职,在新...

    Fundebug

扫码关注云+社区

领取腾讯云代金券