题意: 给你一个大小为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; }