记录编号	162230	评测结果	AAAWAWAWAW
题目名称	786.最长数列	最终得分	60
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	0.881 s
提交时间	2015-05-15 16:48:50	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>

#define LL unsigned long long
#define ipos set<LL>::iterator
#define N 110
#define eps 1e-13

using namespace std;

void file(){
	freopen("series.in","r",stdin);
	freopen("series.out","w",stdout);
}

int n,tot,ans=0;
multiset<LL> T;
LL a[N];
map<LL,int> C;

void check1(LL a1,LL a2){
	int tmp=2;
	LL d=a2-a1,now=a2;
	C.clear();
	for(int i=1;i<=n;i++) C[a[i]]++;
	C[now]--;
	while(C[now+d]){
		now+=d;
		C[now]--;
		tmp++;
	}
	ans=max(ans,tmp);
}

void check2(LL a1,LL a2){
	int tmp=2;
	LL d=a2/a1,now=a2;
	C.clear();
	for(int i=1;i<=n;i++) C[a[i]]++;
	C[now]--;
	while(C[now*d]){
		now*=d;
		C[now]--;
		tmp++;
	}
	ans=max(ans,tmp);
}

LL qpow(LL x,int n){
	LL ans=1;
	for(;n;n>>=1,x*=x) if(n&1) ans*=x;
	return ans;
}

void check3(LL now,int k){
	int tmp=1;
	C.clear();
	for(int i=1;i<=n;i++) C[a[i]]++;
	C[now]--;
	while(C[qpow(now,k)]){
		now=qpow(now,k);
		C[now]--;
		tmp++;
	}
	ans=max(ans,tmp);
}

int Te;

int main(){
	file();
	scanf("%d",&Te);
	while(Te--){
		T.clear(); tot=0; ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			LL x;
			scanf("%llu",&x);
			T.insert(x);
		}
		for(ipos i=T.begin();i!=T.end();i++) a[++tot]=(*i);
		n=tot;
		for(int i=1;i<n;i++){
			for(int j=i+1;j<=n;j++){
				check1(a[i],a[j]);
				if(a[i] && a[j]%a[i]==0) check2(a[i],a[j]);
			}
		}
		for(int i=1;i<=n;i++)
			for(int k=1;k<=32;k++) check3(a[i],k);
		printf("%d\n",ans);
	}
	return 0;
}