记录编号	38478	评测结果	ATTETTTTTT
题目名称	最长数列	最终得分	10
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	8.001 s
提交时间	2012-04-19 18:38:57	内存使用	0.26 MiB

#include <cstdlib>
#include <cstdio>
#include <set>
#include <algorithm>
#include <cmath>
#define MAXN 101
using namespace std;
typedef long long LL;
typedef multiset<LL> mset;
LL Num[MAXN],T,N,maxx,ans;
inline LL Max(int a,int b) {return a>b?a:b;}
LL A,K;  mset Set;

inline LL abss(LL a) {return a>0?a:-a;}

inline LL pow(LL a,LL b)
{
	LL ans=1;
	for(int i=1;i<=b;i++) ans*=a;
	return ans;
}

inline LL check(LL oper)
{
	mset ms;
	if(oper==1)
	{
		LL tmp;  
		for(int i=0;;i++)
		{
			tmp=A+K*i;
			if(abss(tmp)>abss(maxx)) break;
			if(Set.find(tmp)==Set.end()) {return ms.size();}
			ms.insert(tmp);
		}
		return ms.size();
	}
	if(oper==2)
	{
		LL tmp=A; ms.insert(A);
		for(int i=1;;i++)
		{
			tmp=tmp*K;
			if(abss(tmp)>abss(maxx)) break;
			if(Set.find(tmp)==Set.end()) {return ms.size();}
			ms.insert(tmp);
		}
		return ms.size();
	}
	if(oper==3)
	{
		LL tmp=A; ms.insert(A);
		for(int i=1;;i++)
		{
			tmp=pow(tmp,K);
			if(abss(tmp)>abss(maxx)) break;
			if(Set.find(tmp)==Set.end()) {return ms.size();}
			ms.insert(tmp);
		}
		return ms.size();
	}
}

inline bool cmp(const LL&a,const LL&b)
{
	return abss(a)<abss(b);
}

inline void solve()
{
	sort(Num+1,Num+1+N,cmp);
	LL res;
	for(int i=1;i+ans<=N;i++)
	{
		A=Num[i];
		for(int j=i+1;j+ans<=N;j++)
		{
			//Case 1:
			K=Num[j]-A;
			res=check(1);
			ans=Max(ans,res);
			if(ans==N) {printf("%lld\n",ans); return;}
			//Case 2:
			if(Num[j]%A==0)
			{
				K=Num[j]/A;
				res=check(2);
				ans=Max(ans,res);
				if(ans==N) {printf("%lld\n",ans); return;}
			}
			//Case 3:
			if(A==1 || A==0) continue;
			int s=A,m;
			for(m=1;s<abss(Num[j]);m++) 
			{
				s*=A; s=abss(s);
			}
			if(abss(s)!=abss(Num[j])) continue;
			K=m;
			res=check(3);
			ans=Max(ans,res);
			if(ans==N) {printf("%lld\n",ans); return;}
		}
	}
	printf("%lld\n",ans);
}

int main()
{
	freopen("series.in","r",stdin);
	freopen("series.out","w",stdout);
	scanf("%lld\n",&T);
	for(int i=1;i<=T;i++)
	{
		scanf("%lld\n",&N);  maxx=0; ans=1;
		for(int j=1;j<=N;j++) 
		{
			scanf("%lld",Num+j);
			maxx=Max(maxx,abss(Num[j]));
			Set.insert(Num[j]);
		}
		solve();
		Set.clear();
	}
	return 0;
}