C++14(g++5.4) 解法, 执行用时: 2832ms, 内存消耗: 193632K, 提交时间: 2018-08-06 20:36:30

#include<bits/stdc++.h>
using namespace std;
const int maxn=(1<<24)+5;
int dp[maxn],vis[maxn],to[maxn];
int ans,a,b,c,n;
void dfs(int u)
{
    vis[u]=1;
    int v=to[u];
    if(!vis[v])dfs(v);
    else if(vis[v]==1)vis[v]=3;
    dp[u]=dp[v]+1;
    if(vis[u]==3)
    {
        int w=v;
        while(w!=u)
        {
            dp[w]=dp[u];
            w=to[w];
        }
    }
    vis[u]=2;
}
void solve()
{
    scanf("%d%d%d%d",&a,&b,&c,&n);
    ans=0;
    for(int i=0;i<n;i++)
    {
        dp[i]=0;vis[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        int pos=(1ll*a*i*i+b*i+c)%n;
        to[i]=pos;
    }
    for(int i=0;i<n;i++)
    {
        if(!vis[i])dfs(i);
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}

C++(clang++11) 解法, 执行用时: 1480ms, 内存消耗: 193656K, 提交时间: 2020-12-16 21:15:58

#include<bits/stdc++.h>
using namespace std;

int R[17000005],DP[17000005],V[17000005];
void DFS(int x)
{
	int i=R[x];
	if(!V[i])V[i]=1,DFS(i);
	else if(V[i]==1)V[i]=3;
	DP[x]=DP[i]+1;
	if(V[x]==3)while(i!=x)DP[i]=DP[x],i=R[i];
	V[x]=2;
}
int main()
{
    int i,j,x,y,n,ans,T;
    long long a,b,c;
    scanf("%d",&T);
    while(T--)
    {
    	scanf("%lld%lld%lld%d",&a,&b,&c,&n),ans=0;
    	for(i=0;i<n;i++)R[i]=(a*i*i+b*i+c)%n,V[i]=DP[i]=0;
		for(i=0;i<n;i++)if(!V[i])V[i]=1,DFS(i),ans=max(ans,DP[i]);
    	printf("%d\n",ans);
	}
	return 0;
}