A Ana e o Aniceto, dois grandes amigos, gostam muito de tudo o que envolve matemática. Recentemente, estavam a jogar um novo jogo que consistia em descobrir muito rapidamente quantos divisores tem um dado número inteiro positivo. Um divisor é um número inteiro positivo que divide exactamente outro número inteiro positivo, ou seja, d é divisor de n se existir um inteiro q tal que d vezes q é igual a n. Por exemplo, o número 10 tem exactamente 4 divisores (1, 2, 5 e o próprio 10).
Uma vez que são muito rápidos nos cálculos, resolveram complicar um pouco mais o jogo, para o tornar mais desafiante. Em vez de apenas dizerem quantos divisores tem um dado número, têm de dizer quantos números dum dado intervalo têm uma determinada quantidade de divisores. Por exemplo, o jogo pode consistir em dizer rapidamente quantos números entre 1 e 15 têm exactamente 4 divisores. Neste caso a resposta seria 5, pois existem 5 números entre 1 e 15 que têm 4 divisores: 6, 8, 10, 14 e 15.
Depois de seleccionarem previamente a quantidade de divisores, a Ana e o Aniceto definem os intervalos que lhes interessam. O jogo consiste em repetidamente um deles ir definindo um novo intervalo de números e o outro ir respondendo quantos números nesse intervalo têm a quantidade pretendida de divisores.
Tens de ajudar a Ana e o Aniceto fazendo um programa para jogar este jogo!
O Problema
Dado um número D (a quantidade de divisores), N pares de números Ai e Bi, a tua tarefa é descobrir para cada um destes pares quantos números entre Ai e Bi (inclusive, ou seja, no intervalo [Ai,Bi]) têm exactamente D divisores.
Input
Na primeira linha do input vem um único número inteiro D indicando a quantidade de divisores a considerar. Na segunda linha vem um número inteiro N indicando o número de intervalos a considerar.
Seguem-se exactamente N linhas, cada uma contendo exactamente dois números inteiros separados por um espaço: Ai e Bi, indicando que deves considerar números entre esses limites. Os limites do intervalo pertencem ao intervalo.
Output
O output deve ser constituído exactamente por N linhas, cada uma contendo um único número inteiro indicando a quantidade de números no intervalo [Ai,Bi] que têm exactamente D divisores. Estas linhas devem vir pela mesma ordem em que os intervalos aparecem no input.
Restrições
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ D ≤ 100 000 Número de divisores
1 ≤ N ≤ 1 000 Número de intervalos
1 ≤ Ai ≤ Bi ≤ 100 000 Intervalos de números
Nota sobre a avaliação
Para um conjunto de casos de teste valendo 40% dos pontos, o número de intervalos é inferior a 10 e quer a quantidade de divisores, quer os números que limitam o intervalo, são inferiores 1000.
Exemplo de Input
4
5
1 10
1 15
11 15
1 5
20 30
Exemplo de Output
3
5
2
0
4
Editado por quintelab Título alterado conforme regras do Fórum
Pergunta
chulos
A Ana e o Aniceto, dois grandes amigos, gostam muito de tudo o que envolve matemática. Recentemente, estavam a jogar um novo jogo que consistia em descobrir muito rapidamente quantos divisores tem um dado número inteiro positivo. Um divisor é um número inteiro positivo que divide exactamente outro número inteiro positivo, ou seja, d é divisor de n se existir um inteiro q tal que d vezes q é igual a n. Por exemplo, o número 10 tem exactamente 4 divisores (1, 2, 5 e o próprio 10).
Uma vez que são muito rápidos nos cálculos, resolveram complicar um pouco mais o jogo, para o tornar mais desafiante. Em vez de apenas dizerem quantos divisores tem um dado número, têm de dizer quantos números dum dado intervalo têm uma determinada quantidade de divisores. Por exemplo, o jogo pode consistir em dizer rapidamente quantos números entre 1 e 15 têm exactamente 4 divisores. Neste caso a resposta seria 5, pois existem 5 números entre 1 e 15 que têm 4 divisores: 6, 8, 10, 14 e 15.
Número: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Quantidade de divisores: 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4
Depois de seleccionarem previamente a quantidade de divisores, a Ana e o Aniceto definem os intervalos que lhes interessam. O jogo consiste em repetidamente um deles ir definindo um novo intervalo de números e o outro ir respondendo quantos números nesse intervalo têm a quantidade pretendida de divisores.
Tens de ajudar a Ana e o Aniceto fazendo um programa para jogar este jogo!
O Problema
Dado um número D (a quantidade de divisores), N pares de números Ai e Bi, a tua tarefa é descobrir para cada um destes pares quantos números entre Ai e Bi (inclusive, ou seja, no intervalo [Ai,Bi]) têm exactamente D divisores.
Input
Na primeira linha do input vem um único número inteiro D indicando a quantidade de divisores a considerar. Na segunda linha vem um número inteiro N indicando o número de intervalos a considerar.
Seguem-se exactamente N linhas, cada uma contendo exactamente dois números inteiros separados por um espaço: Ai e Bi, indicando que deves considerar números entre esses limites. Os limites do intervalo pertencem ao intervalo.
Output
O output deve ser constituído exactamente por N linhas, cada uma contendo um único número inteiro indicando a quantidade de números no intervalo [Ai,Bi] que têm exactamente D divisores. Estas linhas devem vir pela mesma ordem em que os intervalos aparecem no input.
Restrições
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ D ≤ 100 000 Número de divisores
1 ≤ N ≤ 1 000 Número de intervalos
1 ≤ Ai ≤ Bi ≤ 100 000 Intervalos de números
Nota sobre a avaliação
Para um conjunto de casos de teste valendo 40% dos pontos, o número de intervalos é inferior a 10 e quer a quantidade de divisores, quer os números que limitam o intervalo, são inferiores 1000.
Exemplo de Input
4
5
1 10
1 15
11 15
1 5
20 30
Exemplo de Output
3
5
2
0
4
Editado por quintelabTítulo alterado conforme regras do Fórum
Link para o comentário
Compartilhar em outros sites
0 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.