[JSOI2015]最大公约数

╰+攻爆jí腚メ 2023-10-11 11:20 36阅读 0赞

[题目][Link 1]

一个非常众所周知的结论，一个序列的前缀\\(\\gcd\\)只会有\\(\\log\\)种取值

于是考虑一下一些暴力的东西，我们枚举每个点作为左端点，二分出前缀\\(\\gcd\\)变化的位置，复杂度大概是\\(\\operatorname\{O(nlog^3n)\}\\)，好像非常垃圾的样子

我们考虑直接从后往前枚举左端点，每次往前加入一个数，和之前的前缀\\(\\gcd\\)再取一个\\(\\gcd\\)就好了，同时合并掉相同的一段

复杂度是\\(\\operatorname\{O(nlog^2n)\}\\)，还是挺丢人的

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    inline LL read() {
        char c=getchar();LL x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3ll)+(x<<1ll)+c-48,c=getchar();return x;
    }
    const int maxn=1e5+5;
    LL gcd(LL a,LL b) {return !b?a:gcd(b,a%b);}
    LL a[maxn];
    int n;LL ans;
    LL b[maxn],c[maxn];int p[maxn],top,t[maxn];
    int main() {
        n=read();
        for(re int i=1;i<=n;i++) a[i]=read();
        ans=a[n];b[++top]=ans;p[1]=n;
        for(re int i=n-1;i;--i) {
            for(re int j=top;j;--j)
                b[j]=gcd(b[j],a[i]);
            b[++top]=a[i];p[top]=i;
            int tot=0;
            for(re int j=top-1;j>=0;--j) {
                if(b[j]==b[j+1]) continue;
                c[++tot]=b[j+1],t[tot]=p[j+1];
            }
            top=tot;
            for(re int j=top;j;--j) 
                b[j]=c[top-j+1],p[j]=t[top-j+1],ans=max(ans,1ll*b[j]*(p[j]-i+1));
        }
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11348104.html

[Link 1]: https://www.luogu.org/problem/P5502

发表评论取消回复

表情：

评论列表（有 0 条评论，36人围观）

还没有评论，来说两句吧...

相关阅读

相关 [JSOI2015]最大公约数

[题目][Link 1] 一个非常众所周知的结论，一个序列的前缀\\(\\gcd\\)只会有\\(\\log\\)种取值于是考虑一下一些暴力的东西，我们枚举每个点作为左端

╰+攻爆jí腚メ/ 2023年10月11日 11:20/ 0 赞/ 37 阅读

相关求最大公约数

`迭代版本` function getCd(a, b) { if (a b < 0) return 1 if (a ==0 || b

深碍√TFBOYSˉ_/ 2023年01月04日 10:30/ 0 赞/ 193 阅读

相关最大公约数

什么是最大公约数 > 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（

小灰灰/ 2022年07月29日 06:26/ 0 赞/ 197 阅读

相关最大公约数

public class GCD { //方法一 public static void gcd1(int a, int b) {

左手的ㄟ右手/ 2022年05月26日 01:28/ 0 赞/ 167 阅读

相关最大公约数

问题D：最大公约数时间限制：1秒内存限制：64 MB 提交：554解决：274 \[ [提交][Link 1] \] \[ [状态][Link 2] \] \[

末蓝、/ 2022年05月22日 12:20/ 0 赞/ 223 阅读

相关 __gcd最大公约数

\_\_gcd-最大公约数 1. 最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf） 2

超、凢脫俗/ 2022年05月11日 13:44/ 0 赞/ 222 阅读

相关算法-最大公约数

最大公约数是一个很经典的数学问题，对于这个问题有四种通用的解法，质因数分解法，短除法，不过比较常用的还是辗转相除法，算法出自于欧几里的著作《几何原本》，还有一个就是出自《九章算

爱被打了一巴掌/ 2022年03月31日 17:12/ 0 赞/ 268 阅读

相关求最大公约数

求最大公约数 \\一.题目内容 \\运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块。 \\二.算法设计 \\四种函

以你之姓@/ 2022年03月10日 04:23/ 0 赞/ 308 阅读

相关 [JSOI2008]最大数

这道题是板子题，用来练习线段树。 1 include <bits/stdc++.h> 2 3 using namespace std;

妖狐艹你老母/ 2021年12月21日 21:23/ 0 赞/ 213 阅读

相关 [JSOI2008]最大数

[题目传送门][Link 1] 这道题需要解决的是区间求值和单点修改，可以用线段树求解，首先构造一颗\[1,m\]的“空树”（序列至多有m个数），即每个节点维护的信息均为0，

野性酷女/ 2021年12月10日 10:15/ 0 赞/ 187 阅读