题意: 给你一个大小为n的序列,让你求里面所有子串的GCD,求里面最多有多少不同的GCD。
思路: 利用集合set–tmp维护 到当前子串的最后一个元素的所有GCD,set–ans保存所有不同种类的GCD。
分析一下为什么不会超时,一开始以为这个算法很暴力,觉得是O(n^2 * logn)
其实,我们猜想最暴力的情况 即,1 ,2 , 4, 8 ,16,…… ,2^n 这组数据,我们会以为
1<=n<=5e5,这样子一定非常暴力! 其实!不是!!
为什么呢?因为——-元素ai 要在[1,1e18]这个范围内,所以2^n <= 10^18
两遍同取log2 可以 转换—–> n<= 18log2(10) 这个 数字约等于60,远远小于5e5,所以这个算法复杂度差不多为O(n*18log2(10) * logn)。
AC代码: 临摹超霸ORZ
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) int(x.size()-1)
#define all(x) x.begin(),x.end()
#define rep(i,s,e) for (int i=s;i<=e;i++)
#define rev(i,s,e) for (int i=e;i>=s;i--)
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 5;
LL gcd(LL a,LL b)
{
if(!b) return a;
else return gcd(b,a%b);
}
set<LL> tmp1,tmp2,ans;
set<LL> ::iterator it;
LL a[MAXN];
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin>>n;
rep(i,1,n) cin>>a[i];
int f = 0;
rep(i,1,n)
{
if(f)
{
tmp1.clear();
for(it = tmp2.begin();it!=tmp2.end();it++)
{
LL x = gcd(a[i],*it);
tmp1.insert(x);
ans.insert(x);
}
tmp1.insert(a[i]);
ans.insert(a[i]);
}
else
{
tmp2.clear();
for(it = tmp1.begin();it!=tmp1.end();it++)
{
LL x = gcd(a[i],*it);
tmp2.insert(x);
ans.insert(x);
}
tmp2.insert(a[i]);
ans.insert(a[i]);
}
f ^= 1;
}
cout<<ans.size()<<endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)