首页 > 代码库 > bzoj 4488: [Jsoi2015]最大公约数
bzoj 4488: [Jsoi2015]最大公约数
做这个题的时候蛋疼的想一个知道[l,r]的gcd那[l+1,r]的能不能快速算出来。
然后想了一下发现丝毫没有道理。
于是又扒了题解。
神奇的题解说,一个序列的gcd最多有log个,突然就GG了
诶,遇到这样的题还是多搞几组数据观察一下规律的好
1 #include <bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 inline LL ra() 5 { 6 LL x=0; char ch=getchar(); 7 while (ch<‘0‘ || ch>‘9‘) ch=getchar(); 8 while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} 9 return x; 10 } 11 12 const int maxn=100005; 13 14 struct node{ 15 LL num; int x; 16 bool operator < (const node &y) const {return num<y.num||num==y.num && x<y.x;} 17 }f[2][maxn]; 18 LL a[maxn]; 19 int n; 20 21 LL gcd(LL x, LL y) {return y==0?x:gcd(y,x%y);} 22 23 int main() 24 { 25 n=ra(); 26 for (int i=1; i<=n; i++) a[i]=ra(); 27 int s1=0,s2=0; 28 int p=0,q=1; 29 LL ans=0; node d; 30 for (int i=1; i<=n; i++) 31 { 32 for (int j=1; j<=s1; j++) f[p][j].num=gcd(a[i],f[p][j].num); 33 d.num=a[i]; d.x=i; s1++; f[p][s1]=d; 34 sort(f[p]+1,f[p]+s1+1); 35 s2=0; 36 for (int j=1; j<=s1; j++) 37 if (f[p][j].num!=f[p][j-1].num) 38 f[q][++s2]=f[p][j]; 39 for (int j=1; j<=s2; j++) ans=max(ans,f[q][j].num*(LL)(i-f[q][j].x+1)); 40 p^=1; q^=1; s1=s2; 41 } 42 printf("%lld\n",ans); 43 return 0; 44 }
bzoj 4488: [Jsoi2015]最大公约数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。