2019 ICPC EC Final H（思维）

[题目链接](https://vjudge.net/problem/Gym-102471H) ------------ ------------ ```cpp #include <bits/stdc++.h> using namespace std; const int M=2e5+5; typedef long long ll; int n; map<ll,int> mp; ll p,b[M]; ll qpow(ll a,ll b) { ll y=1; while(b) { if(b&1)y=y*a%p; a=a*a%p; b>>=1; } return y; } int calc(ll q) { unordered_map<ll,int> ump; int res=0; if(q==1) { for(int i=1;i<=n;i++) res=max(res,++ump[b[i]]); return res; } for(int i=n;i>=1;i--) res=max(res,ump[b[i]]=ump[b[i]*q%p]+1); return res; } int main() { int T;scanf("%d",&T); while(T--) { mp.clear(); scanf("%d%lld",&n,&p); for(int i=1;i<=n;i++)scanf("%lld",&b[i]); for(int i=1;i<=n-1;i++) { ll q=b[i+1]*qpow(b[i],p-2)%p; mp[q]++; } for(int i=1;i<=n-2;i++) { ll q=b[i+2]*qpow(b[i],p-2)%p; mp[q]++; } int c=(n-1)/4; int ans=0; for(auto it=mp.begin();it!=mp.end();it++) if(it->second>=c) ans=max(ans,calc(it->first)); if(ans<(n+1)/2)printf("-1\n"); else printf("%d\n",ans); } return 0; } ```