Collatz Conjecture

题目链接：Collatz Conjecture

---

显然有一个3个log的做法。先预处理任意区间的gcd。用ST表即可。

然后枚举每一个作为最后一个位置，往前二分即可。然后是过不了的。

代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,a[N],f[N][20];	unordered_set<int> s;
inline int ask(int l,int r){
	int len=log2(r-l+1);
	return __gcd(f[l][len],f[r-(1<<len)+1][len]);
}
inline void solve(int i){
	int j=i-1; s.insert(a[i]);
	int now=a[i];
	while(j>=1){
		int l=1,r=j;
		while(l<r){
			int mid=l+r+1>>1;
			if(ask(mid,i)!=now)	l=mid;
			else r=mid-1;
		}
		if(ask(l,i)==now)	return ;
		s.insert(now=ask(l,i));
		j=l-1;
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]),f[i][0]=a[i];
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	for(int i=1;i<=n;i++)	solve(i);
	cout<<s.size();
	return 0;
}

---

然后，我们可以发现每个数字往前找gcd的时候，其实是和前面一个数往前面找的找到的值是有关系的。

然后对于每个数字之前能找到的数字的个数都是log的，所以我们就可以两个log来完成了。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,a[N],f1[N],f2[N]; unordered_set<int> s;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]); f2[0]=0;
		for(int j=1;j<=f1[0];j++)	f2[++f2[0]]=__gcd(f1[j],a[i]),s.insert(f2[f2[0]]);
		s.insert(a[i]);	f2[++f2[0]]=a[i];	sort(f2+1,f2+f2[0]+1);
		f1[0]=f2[0]=unique(f2+1,f2+f2[0]+1)-f2-1;
		for(int j=1;j<=f1[0];j++)	f1[j]=f2[j];
	}
	cout<<s.size();
	return 0;
}