BZOJ4488: [Jsoi2015]最大公约数
2024-08-21 11:32:45
Description
给定一个长度为 N 的正整数序列Ai对于其任意一个连续的子序列
{Al,Al+1...Ar},我们定义其权值W(L,R )为其长度与序列中所有元素的最大公约数的乘积,即W(L,R) = (R-L+1) ∗ gcd (Al..Ar)。
JYY 希望找出权值最大的子序列。
Input
输入一行包含一个正整数 N。
接下来一行,包含 N个正整数,表示序列Ai
1 < = Ai < = 10^12, 1 < = N < = 100,000
Output
输出文件包含一行一个正整数,表示权值最大的子序列的权值。
Sample Input
5
30 60 20 20 20
30 60 20 20 20
Sample Output
80
//最佳子序列为最后 4 个元素组成的子序列。
//最佳子序列为最后 4 个元素组成的子序列。
固定端点的序列一共只有O(logn)种不同的gcd,所以我们枚举右端点,维护不同gcd的左端点集合,右端点改变时重新扫一遍合并一下相同的gcd区间即可。
时间复杂度为O(Nlog^2N)。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
typedef long long ll;
inline ll read() {
ll x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=100010;
ll A[maxn],B[maxn],ans;
ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}
int n,S[maxn];
int main() {
n=read();int top=0;
rep(i,1,n) A[i]=read();
rep(i,1,n) {
S[++top]=i;B[top]=A[i];
dwn(j,top-1,1) {
B[j]=gcd(B[j],B[j+1]);
if(B[j]==B[j+1]) {
rep(k,j+1,top-1) S[k]=S[k+1],B[k]=B[k+1];
top--;
}
}
rep(j,1,top) ans=max(ans,B[j]*(i-S[j]+1));
}
printf("%lld\n",ans);
return 0;
}
最新文章
- Hadoop 2.x 生态系统及技术架构图
- 《Web开发中让盒子居中的几种方法》
- 让一个端口同时做两件事:http/https和ssh
- Kernel Methods (1) 从简单的例子开始
- C# 时间函数
- Gridview导出到Excel
- iOS所有常用证书,appID,Provisioning Profiles配置说明及制作图文教程
- websocket介绍
- shell之九九乘法表
- Linux 下 HTTP连接超时
- 【Android 应用开发】 ActionBar 基础
- InetAddress and InetSocketAddress
- netty入门(一)
- 记录ThreadPoolTaskExecutor线程池的在项目中的实际应用,讲解一下线程池的配置和参数理解。
- mysql清理binlog日志
- Django登陆以后重定向到请求登陆的页面
- 转:JAVA中解决Filter过滤掉css,js,图片文件等问题
- Java中的boxing和unboxing(转)
- WinRAR 5.40 &; 4.20 &; 3.93 的注册码 - rarreg.key
- Python数据分析--Pandas知识点(二)