Dashboard - 2017 Benelux Algorithm Programming Contest (BAPC 17) - Codeforces
大意:给n个数字,求区间gcd的情况数
首先,设我们有三个数字 a b c
gcd(a,b)==d,gcd(b,c)==e,gcd(d,e)==f
因为gcd(b,b)==b,gcd(gcd(a,b),gcd(b,c))=gcd(a,b,c,d)=gcd(a,b,c)
所以我们可以把所有的区间gcd写成一个倒三角形,下面的是上面俩的gcd
9 6 2 4
3 2 2
1 2
1
去重完就只有9 6 4 3 2 1结果为6
完毕
怎么可能这么简单
留个伏笔,因为我也没搞清楚这个算法为啥能过
如果有某一行的很多个数字是一样的,他们gcd的值都是本身,和边上gcd的值也唯一,所以可以省略为一个
#include<bits/stdc++.h> using namespace std; #define int long long const int N=5e5+5; int ans[N]; int num[N]; int f1[N]; int f2[N]; int n,l=0; unordered_set<int> s; long long gcd(long long a,long long b) { if(b==0) return a; else return gcd(b,a%b); } signed main(){ std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>num[i]; s.insert(num[i]); } int t=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n-i+1-l;j++)// { if(i%2==1) { f1[j-t]=gcd(num[j],num[j+1]); if(f1[j-t]==f1[j-t-1]) { f1[j-t]=0;t++; } else { s.insert(f1[j-t]); } } else { num[j-t]=gcd(f1[j],f1[j+1]); if(num[j-t]==num[j-t-1]) { num[j-t]=0; t++; } else { s.insert(num[j-t]); } } } l+=t; t=0; } cout<<s.size()<<"\n"; }