0

Estou fazendo um programa em C++ para resolver o exercício 2597 de matemática da plataforma URI ONLINE JUDGE segue abaixo a descrição do problema.

inserir a descrição da imagem aqui

Eu comecei a fazer o programa em C++, porém percebam que a entrada é muito grande, tentei fazer uma DP para pré-processar tudo antes, porém não consigo criar um vetor de tamanho 10^9 !! Segue o programa para vocês darem uma olhada **

#include <bits/stdc++.h>
using namespace std;
typedef long long int bigint;

 bigint contaDiv(bigint dividendo) {

 bigint div = 0;
 bigint k = 1;
 bigint m = 1;
 bigint divisor = 1;

 while(divisor<=sqrt(dividendo))
  {

        if(dividendo%divisor==0)
        {
//              cout<<"(div/div)"<<(dividendo/divisor)<<endl;

            if((dividendo/divisor)==divisor)
            {
                div+=1;// cout<<"one"<<endl;
            }
            else
            {
                div+=2; //cout<<"two"<<endl;
            }

        }

        ++divisor;
}
return div;
}

int main(void) {

ios_base::sync_with_stdio(0);
cin.tie(0);

bigint c,n,vl;
cin>>c;


while(c--) {

    cin>>n;

    int ans = 0;

    for(int i=1;i<=n;++i) {
//          cout<<"DIV de "<<i<<" = "<<contaDiv(i)<<endl;
        if(contaDiv(i)%2==0) {
            ++ans;
        }
    }

    cout<<ans<<endl;
}

return 0;
}

**Se alguém conseguir me dar uma ajuda... como resolver esse problema !! No momento esse código esta recebendo Time Limit Exceed !! **

1 Resposta 1

4

O seu problema é um problema de fatoração de números. O problema da fatoração é um problema considerado difícil. Mas considerando-se que N <= 109, então o número não poderá ter divisores maiores que sqrt(109) = 31622 que não seja ele mesmo, e com isso, esse limite de 31622 é na verdade um limite pequeno e fácil de ser explorado.

Você está realizando divisões por todos os números no intervalo de 1 até a raiz quadrada do número. No entanto, uma opção melhor é fazer a divisão apenas pelos números primos nesse intervalo a fim de montar-se a fatoração do número e então contar o número de fatores. Existem 3401 primos entre 2 e 31622 (o maior é 31607).

Primeiramente você pode montar uma tabela de números primos. Você pode ou montar essa tabela no começo do programa sempre que ele executar ou criar um outro programa para criar essa tabela e copiar e colar ela direto no código.

Tendo a tabela de números primos, você pode usá-la para fatorar um número e então contar quantos fatores um número tem, conforme o que é delineado aqui.

Ao evitar a divisão por números que não são primos, você deverá evitar muitas divisões que seriam inúteis.

Com essa abordagem, o limite superior para o número de divisões que você faria seria de 3401 + k divisões, onde k é o número de fatores primos encontrados, que seria limitado a log2 n, que é algo próximo a 30 no pior caso. Portanto, é impossível que você tenha que realizar mais que 3431 divisões para qualquer número da entrada. Esse limite é um tanto frouxo, e o limite superior real deve ser menor que isso. Para o número 316072 = 999.002.449 será preciso 3402 divisões. Então você tem algo entre 3402 e 3431 divisões no pior caso. Compare isso com o que você tinha antes, onde você fazia 31622 divisões no pior caso.

2
  • Bom.... eu resolvi !! Olha amigo, talvez de certo esse pensamento... mas eu acho que não ainda não vai dar.. O uri está rejeitando operações sequenciais... Mesmo sendo apenas 3402 no pior caso... Imagine que para cada entrada C, eu digite o maior número possível que é 10^9 ?? Eu teria que percorrer de 1 até 10^9 toda vez, e isso custaria muito.. E não passaria também. Eu consegui resolver encontrando uma lógica por trás desse problema.. Tem uma propriedade de crescimento dos números engraçada..
    – Victor OCV
    Commented 6/08/2018 às 15:21
  • 1
    @VictorOCV Você não tem que percorrer até 10^9 e foi exatamente isso o que eu disse na minha resposta. Commented 6/08/2018 às 16:10

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .