## 113 - Power of Cryptography

**Moderator:** Board moderators

### I am not sure you should write this

I really don`t think that it is good to ask such a questions here. After all, if algorith is esential part of the problem.

Any way I will give you a hint. There is NO number theory for this problem. Just (almost) brute force.

Any way I still think that such question should not be asked here.

Any way I will give you a hint. There is NO number theory for this problem. Just (almost) brute force.

Any way I still think that such question should not be asked here.

### #113

I submit two variations of code to judge - first solution terminates if p == 0, second does not make this check. First solution gets WA (I think because p == 0). Second - TLE (my solution runs forever, if p == 0). I think problem here is with my input method. Can anybody find an input that will cause my code to run forever or print WA? Input should follow input rules provided in problem description http://acm.uva.es/p/v1/113.html.

One more time: my code is sure that first judge's input for p is 0...

By the way, my solution solves samples correctly.

[cpp]#include <iostream.h>

#include <stdio.h>

const unsigned long base = 10000;

const unsigned long N = 100;

struct my_long{

unsigned long digit[N];

};

my_long incr[N*8];

int lll(my_long in){

int i = N;

while((!in.digit

One more time: my code is sure that first judge's input for p is 0...

By the way, my solution solves samples correctly.

[cpp]#include <iostream.h>

#include <stdio.h>

const unsigned long base = 10000;

const unsigned long N = 100;

struct my_long{

unsigned long digit[N];

};

my_long incr[N*8];

int lll(my_long in){

int i = N;

while((!in.digit

*)&&(i > 0)) i--;*

return i;

}

void print(my_long &ml){

int i = N - 1;

while((!ml.digitreturn i;

}

void print(my_long &ml){

int i = N - 1;

while((!ml.digit

*) && (i > 0)) i--;*

cout << ml.digitcout << ml.digit

*;*

i--;

while(i >= 0){

if(ml.digiti--;

while(i >= 0){

if(ml.digit

*< 1000) cout << "0";*

if(ml.digitif(ml.digit

*< 100) cout << "0";*

if(ml.digitif(ml.digit

*< 10) cout << "0";*

cout << ml.digitcout << ml.digit

*;*

i--;

};

cout << endl;

}

void shift(my_long &ml){

for(int i = 0; i < N; i++){

ml.digit[i + 1] += ml.digiti--;

};

cout << endl;

}

void shift(my_long &ml){

for(int i = 0; i < N; i++){

ml.digit[i + 1] += ml.digit

*/base;*

ml.digitml.digit

*%= base;*

}

}

void add(my_long &ml, unsigned long in){

ml.digit[0] += in;

shift(ml);

}

void add(my_long &in1, my_long &in2){

for(int i = 0; i < N; i++) in1.digit}

}

void add(my_long &ml, unsigned long in){

ml.digit[0] += in;

shift(ml);

}

void add(my_long &in1, my_long &in2){

for(int i = 0; i < N; i++) in1.digit

*+= in2.digit[i];*

shift(in1);

}

void mult(my_long &ml, unsigned long in){

for(int i = 0; i < N; i++) ml.digit[i] *= in;

shift(ml);

}

void move_left(my_long &ml, int in){

int i;

for(i = N - 1; i >= in; i--) ml.digit[i] = ml.digit[i - in];

for(i = i; i >= 0; i--) ml.digit[i] = 0;

}

void mult(my_long &in1, my_long in2){

my_long out;

for(int i = 0; i < N; i++) out.digit[i] = 0;

my_long temp;

for(int i = 0; i < (N/2 - 3); i++){

temp = in1;

mult(temp,in2.digit[i]);

move_left(temp,i);

add(out,temp);

}

in1 = out;

}

int power(my_long &n, int pow){

my_long temp;

temp = n;

for(int i = 1; i < pow; i++) mult(n,temp);

return 1;

}

void create_incr(){

my_long temp;

for(int i = 0; i < N; i++) temp.digit[i] = 0;

temp.digit[0] = 1;

for(int i = 0; i < N*8; i++){

incr[i] = temp;

mult(temp,3);

}

}

int less_or_equal(my_long in1, my_long in2){

for(int i = N - 1; i >= 0; i--){

if(in1.digit[i] < in2.digit[i]) return 1;

if(in1.digit[i] > in2.digit[i]) return 0;

}

return 1;

}

int equal(my_long in1, my_long in2){

for(int i = 0; i < N; i++) if(in1.digit[i]!=in2.digit[i]) return 0;

return 1;

}

my_long p,answer,temp;

unsigned long n;

char buffer[200];

void find_answer(){

int i,flag;

for(int i = 0; i < N; i++) temp.digit[i] = 0;

answer = temp;

while(1){

i = 0;

do{

temp = answer;

add(temp,incr[i]);

flag = power(temp,n);

if(equal(temp,p)){

add(answer,incr[i]);

print(answer);

return;

}

i++;

}while((less_or_equal(temp,p))&&(flag));

add(answer,incr[i - 2]);

}

}

int main(){

int k;

create_incr();

while(cin >> n){

gets(buffer);

k = 0;

for(int i = 0; i < N; i++) p.digit[i] = 0;

while(buffer[k]){

mult(p,10);

add(p,buffer[k] - 48 );

k++;

}

if((p.digit[0] == 0)&&(lll(p) < 1)) return 0; //This line checks if p == 0 *********

find_answer();

}

return 0;

}[/cpp]shift(in1);

}

void mult(my_long &ml, unsigned long in){

for(int i = 0; i < N; i++) ml.digit[i] *= in;

shift(ml);

}

void move_left(my_long &ml, int in){

int i;

for(i = N - 1; i >= in; i--) ml.digit[i] = ml.digit[i - in];

for(i = i; i >= 0; i--) ml.digit[i] = 0;

}

void mult(my_long &in1, my_long in2){

my_long out;

for(int i = 0; i < N; i++) out.digit[i] = 0;

my_long temp;

for(int i = 0; i < (N/2 - 3); i++){

temp = in1;

mult(temp,in2.digit[i]);

move_left(temp,i);

add(out,temp);

}

in1 = out;

}

int power(my_long &n, int pow){

my_long temp;

temp = n;

for(int i = 1; i < pow; i++) mult(n,temp);

return 1;

}

void create_incr(){

my_long temp;

for(int i = 0; i < N; i++) temp.digit[i] = 0;

temp.digit[0] = 1;

for(int i = 0; i < N*8; i++){

incr[i] = temp;

mult(temp,3);

}

}

int less_or_equal(my_long in1, my_long in2){

for(int i = N - 1; i >= 0; i--){

if(in1.digit[i] < in2.digit[i]) return 1;

if(in1.digit[i] > in2.digit[i]) return 0;

}

return 1;

}

int equal(my_long in1, my_long in2){

for(int i = 0; i < N; i++) if(in1.digit[i]!=in2.digit[i]) return 0;

return 1;

}

my_long p,answer,temp;

unsigned long n;

char buffer[200];

void find_answer(){

int i,flag;

for(int i = 0; i < N; i++) temp.digit[i] = 0;

answer = temp;

while(1){

i = 0;

do{

temp = answer;

add(temp,incr[i]);

flag = power(temp,n);

if(equal(temp,p)){

add(answer,incr[i]);

print(answer);

return;

}

i++;

}while((less_or_equal(temp,p))&&(flag));

add(answer,incr[i - 2]);

}

}

int main(){

int k;

create_incr();

while(cin >> n){

gets(buffer);

k = 0;

for(int i = 0; i < N; i++) p.digit[i] = 0;

while(buffer[k]){

mult(p,10);

add(p,buffer[k] - 48 );

k++;

}

if((p.digit[0] == 0)&&(lll(p) < 1)) return 0; //This line checks if p == 0 *********

find_answer();

}

return 0;

}[/cpp]

Code: Select all

```
2
number 100 digits long
```

Do you mean Judge don't have such inputs, so I can use just doubles or long doubles to get AC? (Without implementing long numbers arithmetic)

PS: I can write a code that will solve samples, using only long double, but that code will not solve inputs described above...

p might be very large, but k is not.

we use k=exp(ln(p)/n)

since k is guarateed to be integer, the precision of p from input will be neglected, for p to be large, n need to be large also and k is always a small number <=10^9

since n is large when p is large, then k^n and k^(n+/-1) will have a big difference.

unsigned long double will be find.

Anyway, if anybody can test my solution and find an input resulting in WA or TLE, that would be great.

When I had problems with 105 someone told me that #105 is the easiest problem he was so wrong.

my AC'd code:

[cpp] while(cin >> n >> p) cout << pow(p,1/n) << endl;[/cpp]

I can't understand what a problem like this do in problem set .

with long double we can get input more than 100 digit.

Hisoka is right - of cause we can get that input (using double we can get 308 digit input), but with finite precision.

By the way, there is no solution in the world that will guarantee you infinite precision.

[cpp]double d;

cin >> d;[/cpp]

try this code it will prove you all you want.

You can get maximum 24 digits if you put an integer in 80bit.

In practice you will not get even 20 significant digits. But some information taken from up to 308 digits will be stored in double.

### Off subject

If anyone has test data and correct answers for 173, that would be of a big help. I keep getting a wrong answer, but the problem here is not the messages being correct, but the order of the messages that I am concerned about.

### Really Big Numbers in Java

What's the data type that supports the biggest numbers in java? Is it double? I'm getting WA from the judge and I guess it's because of that.....

Thanks,

joao sarmento

Thanks,

joao sarmento

-----------------

Jo

Jo

There is a class that supports such a big integer: java.math.BigInteger; but there is a problem:

This class isn't supproted yet in the judge compiler; (I think) judge compliler supports only JDK1.1 classes, and BigInteger is JDK1.2 feautre