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