113 - Power of Cryptography

[darksk4]

What's the error in this code?

Code: Select all

I see thanks brianfry713 

[brianfry713]

You need to set the precision so that only integers are displayed.

[salman2972]

i tried to solve that problem in matlab it worked!!!

Code: Select all

clear all
close all
clc

%round;ceil;floor;
y=7;
x=4357186184021382204544;
n=4;
p=16;

% check if the n or p in float type then exit

con1=((n-floor(n))&&(n-floor(n)));
con2=((p-floor(p))&&(p-floor(p)));
if(~(con1&&con2))
k=exp(log(p)/n);
%round(k)
else
    disp('the inputs must be the intiger values')
end


con3=((k-floor(k))&&(k-floor(k)));

if(~con3)
    k
else
    disp('the value of k is not an intiger  please try another combination')
end

please let me know if i can make it better...

[caiomcg]

Hey guys.

I am having a problem in the time limit.
Can you guys have a look?
Probably not the best code

http://pastebin.com/m2tEjeEM

Thanks

[brianfry713]

Output pow(p, 1.0 / n));

[caiomcg]

Thank You!

But, I don´t understand this expression, can you explain it to me?

Regards

[brianfry713]

pow(p, 1.0 / n)) is the same as the nth root of p.

[caiomcg]

I got it lol, thank you Brian!

[arash]

why I get wa by this code ?

Code: Select all

int main() {
    long double p,n;
    while (cin >> n >> p) {
        cout << round(powl(p, (1.0/n))) << endl;
    }
    return 0;
}

[brianfry713]

cout << (int)round(powl(p, (1.0/n))) << endl;

[uDebug]

pow(p, 1.0 / n)) is the same as the nth root of p.

Right. So I came to the same conclusion before I looked at this thread but then I'm not sure how to go about doing this because p could be as large as 10^100 - and so surely a long double's not going to be able to store p. It occurred to me that I could employ BigInt in Java but the pow function doesn't allow for doubles in the exponent - just ints.

Did I miss something?

Update:

Looks like, foo asked the same question in the following thread here

http://acm.uva.es/board/viewtopic.php?f ... 8d#p205142

brianfry713's reply in that thread is

double has enough precision for the I/O in the judge for this problem.

P.S: Edited post and added link where the precision piece is clarified after finding that the question's already been addressed.

[liya]

WA.....

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
  double n,p,k;

while((scanf("%lf %lf",&n,&p))!=EOF)
{
k=pow(p,(1.0/n));
printf("%.0lf\n",k);

}
return 0;


}

[brianfry713]

That is AC code.

[Robur_131]

The following code gives AC when the EPS is between 1e-10 and 1e-15. But if EPS is greater than 1e-10 or less than 1e-15, then it gives WA. Why is that? I though the double mantissa is represented by ~16 digits.

Code: Select all

#include <iostream>
#include <cmath>

int check(int n, double p, int check_value){
    int exponentCheck, exponentTarget;
    double mantissaCheck = frexp(check_value, &exponentCheck);
    double mantissaTarget = frexp(p, &exponentTarget);

    double mantissaCheckRaisedToPowerN = std::pow(mantissaCheck, n);
    double multiplier = 0.5 / mantissaCheckRaisedToPowerN;
    int powerToSubtract = static_cast<int>(std::ceil(std::log2(multiplier)));
    int exponentProduct = exponentCheck * n - powerToSubtract;

    if(exponentProduct < exponentTarget) return -1;
    if(exponentProduct > exponentTarget) return 1;

    double mantissaProduct = mantissaCheckRaisedToPowerN * std::pow(2, powerToSubtract);
    double difference = std::abs(mantissaProduct - mantissaTarget);

    constexpr double EPS = 1e-10; // works between 1e-10 and 1e-15
    if(difference < EPS) return 0;
    if(mantissaProduct < mantissaTarget) return -1;
    return 1;
}

int binarySearch(int n, double p){
    int low = 1, high = 1e9;
    int ans = -1;
    while(low <= high){
        int mid = (low + high) / 2;
        int status = check(n, p, mid);
        if(!status){
            ans = mid;
            break;
        } else if(status == -1){
            low = mid + 1;
        } else{
            high = mid - 1;
        }
    }
    return ans;
}

int main(int argc, char const *argv[])
{
    int n;
    double p;
    while(std::cin >> n >> p){
        // double rhs = std::log(p) / n;
        // double k = std::exp(rhs);
        // std::cout << static_cast<int>(std::nearbyint(k)) << '\n';
        std::cout << binarySearch(n,p) << '\n';
    }
    return 0;
}