Procurando pseudo-aleatórios modulados

Preâmbulo

A pacata cidade de South Park nada de pacata tem. ~~Butters~~, digo, Professor Chaos está aterrorizando mais uma vez! Ele busca o que ninguém jamais procurou, as ocorrências de alguns números pseudo-aleatórios modulares!

O desejo de professor Chaos é muito simples. Ele possui duas sementes para geração de números pseudo-aleatórios e precisa saber quantas ocorrências de alguns números ocorrem a cada $100000$ (isso mesmo cem mil) gerações de números pseudo-aleatórios para as duas sementes que ele possui.

Entrada

A entrada possui um único caso de teste contendo um número indeterminado de linhas.

A primeira possui dois números inteiros sem sinal, $S1$ e $S2$ , representanto, respectivamente, a primeira semente e a segunda semente.

Use rand_r() para gerar os números pseudo-aleatórios

Depois da primeira linha existirão diversas linhas contendo dois inteiros $M_i$ e $B_i$ , representando, respectivamente, MÓDULO (em C representado pelo sinal %) e o número que seja se procurar.

Saída

Para cada linha contendo $M_i$ e $B_i$ você deve responder quantas ocorrências de $B_i$ aconteceram para cada um dos $200000$ números ( $100000$ de cada semente) pseudo-aleatórios módulo $M_i$ .

TAREFA

Você já deve ter percebido que esse problema talvez funcione mais rapidamente se for utilizado o conceito de threads e semáforos.

Exemplo ilustrativo

Para simplificar o entendimento, vou explicar nesta seção um exemplo reduzido, que ao invés de gerar $100000$ valores, geraremos somente $5$ .

Caso a entrada fosse:

300 801 (ref:sementes)
8 6
512 100

Na linha (sementes), recebemos duas sementes, $300$ e $801$ . Gerando $5$ números pseudo-aleatórios com essas sementes, teríamos:

1179231837 1613409366 312769636 1637092777 840974024
1471841391 193279630 141119683 166125014 238450767

A primeira linha os números gerados da semente $300$ e a segunda dos números de $801$ . Nunca modifique esses números, pois eles serão utilizados para toda as outras consultas.

Agora precisaríamos processar as próximas linhas, o primeiro $M_i$ é $8$ que busca a quantidade de ocorrências de $6$ , calculando o MOD $8$ para cada pseudo-aleatório (gerados e armazenaods anteriormente) teríamos:

5 6 4 1 0
7 6 3 6 7

Já que queremos saber a quantidade de ocorrências de $6$ , obtemos 3 ocorrências. Portanto, imprime $3$ .

Já para a segunda linha com $M_i$ $512$ buscando ocorrências de $100$ . Teríamos os seguintes números em módulo $512$ , calculados dos números pseudo-aleatórios do primeiro passo:

93 86 100 425 200
184 259 385 368 13

Neste caso temos somente uma ocorrência de $100$ , portanto imprimiria $1$ .

Tentativa de Professor Chaos

Nosso amigo Chaos possui uma quase implementação, pena que muitos passos estão faltando.

void calcula_perguntas(unsigned int s)
{
    int v[MAXRANDOM];
    for(int i=0;i<MAXRANDOM;i++)
        v[i]=rand_r(&s);
    int mi,bi;

    while(ESPERA(mi,bi))
    {
        conta=0;
        for(int i=0;i<MAXRANDOM;i++)
            if(v[i]%mi==bi)
                conta++;
        somaglobal+=conta;
        CALCULOFEITO
    }
}

int main(void)
{
    leia(s1,s2);
    cria_thread(calcula_perguntas,s1);
    cria_thread(calcula_perguntas,s2);
    while(leia(mi,bi))
    {
        LIBERATHREADS;
        AGUARDECALCULOTHREADS;
        printf("%d\n",somaglobal);
    }
}

LTT

A abordagem feita por Chaos é muito ingênua e deve demorar bastante em entradas maiores. Uma abordagem parecida com produtor-consumidor é mais adequada, algo como feito no exercício do get_ticket.

Limites

$0 \leq S1 \leq S2 \leq 2^{31}$
$0 < B_i < M_i \leq 2^{31}$
Sabemos também que não haverão mais de $2000$ perguntas

Exemplos

Exemplo de entrada

100 200
8 7
256 7
1000000 533

Saída para o exemplo acima

24961
734
0

Exemplo de entrada

Saída para o exemplo acima

Exemplo de entrada

27809 12061
365 19
975 42
525 154
18 0
384 236
291 27
950 785
290 141
183 20
904 268

Saída para o exemplo acima

Exemplo de entrada

Saída para o exemplo acima

Author: Bruno Ribas