C++ 解法, 执行用时: 766ms, 内存消耗: 37496K, 提交时间: 2022-07-07 16:56:49

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+12;

int n;
long long p;
long long inv[N],b[N];
long long qpow(long long a,long long b) 
{
	long long s=1;
	while(b) 
	{
		if(b&1) s=(s*a)%p;
		a=a*a%p;
		b>>=1;
	}
	return s;
}
map<long long,long long> used;

long long check(long long now) 
{
	map<long long,long long> t;
	long long num=0;
	for(int i=n;i>=1;i--) 
	{
		t[b[i]]=t[b[i]*now%p]+1;
		num=max(num,t[b[i]]);
	}
	return num;
}
int main()
{
	int T;
	cin>>T;
	while(T--) 
	{
		used.clear();
		cin>>n>>p;
		for(int i=1;i<=n;i++) cin>>b[i];
		for(int i=1;i<=n;i++) inv[i]=qpow(b[i],p-2);
		
		for(int i=2;i<=n;i++) used[inv[i-1]*b[i]%p]++;
		for(int i=3;i<=n;i++) used[inv[i-2]*b[i]%p]++;
		map<long long,long long>::iterator it;
		long long ans=-1;
		for(it=used.begin();it!=used.end();it++) 
		{
			if(it->second>=n/8) 
			{
				ans=max(ans,check(it->first));
			}
		}
		if(ans*2<n) ans=-1;
		printf("%lld\n",ans);
	}


	return 0;
}

C++14(g++5.4) 解法, 执行用时: 759ms, 内存消耗: 4036K, 提交时间: 2020-01-12 18:56:45

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
std::mt19937 rnd(time(0));
int T,a[N],n,p,dp[N],res;
unordered_map<int,int> mp;
inline int qmi(int a,int b=p-2){
	int res=1;
	while(b){if(b&1) res=res*a%p; a=a*a%p; b>>=1;}
	return res;
}
inline int solve(int l,int r){
	int res=2;
	int q=a[r]*qmi(a[l])%p,inv=qmi(q);
	for(int i=r+1,pre=a[r];i<=n;i++)	if(pre*q%p==a[i])	pre=a[i],res++;
	for(int i=l-1,pre=a[l];i>=1;i--)	if(a[i]*q%p==pre)	pre=a[i],res++;
	return res;
}
signed main(){
	ios::sync_with_stdio(false);	cin.tie(nullptr);
	cin>>T;
	while(T--){
		cin>>n>>p; res=0;
		for(int i=1;i<=n;i++)	cin>>a[i];
		for(int i=1;i<=80;i++){
			int x=rnd()%(n-1)+1;
			for(int j=x+1;j<=n&&j<=x+2;j++)	res=max(res,solve(x,j));
		}
		if(res<(n+1)/2)	cout<<-1<<'\n';
		else	cout<<res<<'\n';
	}
	return 0;
}