TEMA

PROBLEM 1716 - URI Fórum 1.0

URI Online Judge preguntado 6 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Carlos Vinícius respondido 5 years ago

    Segue algumas dicas para otimizar seu algoritmo:

    1 - Utilize o crivo de eratóstenes para encontrar o valor de P de forma mais rápida; 2 - Utilize o algoritmo de euclides estendido para calcular o inverso multiplicativo de E; 3 - Para calcular a potência C^D, utilize o algoritmo "exponentiation by squaring", que tem complexidade O(log(D)).

  • Unknown respondido 5 years ago

    Estou Recebendo 10% WA , já modifiquei algumas coisas do código mas não consigo encontrar o erro. Todo caso que testo resulta no mesmo do toolkit.

    #include <cstdlib>
    #include <iostream>
    #include <set>
    #include <cmath>
    #include <cstdio>
    
    using namespace std;
    
    typedef unsigned long long int llint;
    
    llint j=6LL;
    
    llint verify(llint v[],llint k){
        llint i=0LL;
        while(v[i]!=-1LL){
            if(k%v[i]==0LL){
                return 0LL;
            }
            i++;
        }
        return 1LL;
    }
    llint crivo(llint N,llint v[]){
        v[0LL]=2LL;v[1LL]=3LL;v[2LL]=5LL;v[3LL]=7LL;v[4LL]=11LL;v[5LL]=13LL;v[6LL]=-1LL;
        for(llint i=15LL;i<floor(sqrt(N));i+=2LL){
            if(verify(v,i)==1LL){
                if(N%i==0LL){
                    return (i-1LL)*((N/i)-1LL);
                } 
                v[j]=i;
                j++;
                v[j]=-1LL;
            }
        }
        return N-1LL;
    
    }
    
    pair<llint, pair<llint, llint> > extendedEuclid(llint a, llint b) {
        llint troca=0LL;
        if(a>b){
            b=troca;
            b=a;
            a=troca;
        }
        if(a == 0LL) return make_pair(b, make_pair(0LL, 1LL));
        pair<llint, pair<llint, llint> > p;
        p = extendedEuclid(b % a, a);
        return make_pair(p.first, make_pair(p.second.second - p.second.first*(b/a), p.second.first));
    }
    
    llint modInverse(llint a, llint m) {
        return (extendedEuclid(a,m).second.first + m) % m;
    }
    
    llint expt(llint x, llint n,llint M){
        if (n < 0LL){
          x = 1LL / x;
          n = -n;
        }
        if (n == 0LL) return 1LL;
        llint y=1LL;
        while (n > 1LL){
            if (n%2==0LL){
                x = (x * x)%M;
                n = n / 2LL;
            }
            else{
                y = (x * y)%M;
                x = (x * x)%M;
                n = (n-1LL)/2LL;
            }
        }
        return (x*y)%M;
    }
    
    int main(){
        llint N,E,C,phiN=0LL,D;
        scanf("%lld %lld %lld",&N,&E,&C);
        llint H=floor(sqrt(N));
        llint v[H];
        phiN=crivo(N,v);
        D=modInverse(E,phiN);
        cout<<expt(C,D,N)<<endl;
        return 0;
    }
  • Johnnes Santos respondido 6 years ago

    Estou com problemas neste exercicio, recebo Time limit exceeded e gostaria de saber uma maneira de otimizar este algoritmo. Todos os casos testes funcionaram, porém está estourando o tempo sendo que calculando o tempo em ms com a biblioteca ctime não chega a 1s, não sei mais o que fazer.

    #include<iostream>
    using namespace std;
    
    int fator(int i,int N){    // Função que encontra o valor de P
        if(N%i == 0){
            return i;
        }else{
            return fator(i+2,N);    // Como são valores são primos impares calculo 
        }                                         apenas com os valores impares.
    }
    
    int totiente(int N){    // Função responsavel por calcular o totiente
        int P = fator(3,N);   // Inicio do 3 pra encontrar 3 pois (15<=N).
        int Q = N/P;            // se N = PQ e sabendo P temos que Q = N/P.
        return (P-1)*(Q-1);
    }
    
    int D(int N, int E){        // Calcula a chave pra descriptografar a mensagem 
        int tot;
        unsigned long long int c=1;       //Devo utilizar (unsigned long long) pois a condição 
        tot = totiente(N);                           do while pode estourar o int.
        while(c*E%tot != 1){    //DE = 1 (mod φ(N)) para Calcular D utilizo a variavel c.
            c++;
        }
        return c;
    }
    
    int mensagem(int N, int E, int C){   //Descriptografar a mensagem
        int i;
        unsigned long long int m=1;
        int d = D(N,E);
        for(i=0;i<d;i++){    // M = Cd (mod n) definitivamente usar isso estoura  qualquer 
            m = m*C % N;        tipo de inteiro par  valores altos. Então calculo 1 a 1. 
        }
        return m;
    }
    
    int main(){
        int N,E,C;
        cin>>N>>E>>C;
        cout<<mensagem(N,E,C)<<endl;
        return 0;
    }

    Caso teste que eu estava utilizando: N = 30631189 E = 997 C = 1680017 Mensagem = 10