Autor da análise: piva
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2381
Resumo
Dados, $a$, $R0$, $c$ e $m$, e um gerador de números com a seguinte propriedade $R[n] = (a*R[n - 1] + c)%m$, devolver a maior diferença entre dois números gerados tal que não exista nenhum outro número entre eles.
Solução
Notamos inicialmente que $m <= 16*10^6$. Pelo princípio da casa dos pombos, só podemos gerar $16*10^6$ números distintos, o que é pequeno e rápido de ser gerado. Note que pelo enunciado, não precisamos usar long long (o que pode dar TLE, já que operações com long long são mais demoradas), basta gerar usando $R[n] = ((A*R[n-1])%m + c%m) %m$ (mod é distributivo).
Agora nos resta apenas usar uma estrutura tal que consigamos achar o valor pedido em tempo linear. Podemos usar um vetor booleano $V$ (inicialmente todo falso) e conforme geramos os números $R[i]$, marcamos $V[ R[i] ] = true$. Assim que gerarmos um $R[i]$ tal que $V[ R[i] ] == true$, podemos parar. Depois, é só percorrer o vetor mantendo o índice do último número gerado e ir atualizando a resposta.
Discuta o problema