113 - Power of Cryptography

Moderator: Board moderators

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Try the formula:
a log b = log b / log a

PS: a in a log b is the base of the log. So when a=2 and b=16,
then a log b is 4 since a^4=b.
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Why not using the pow() function.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
why would you?
the formula exp( log(p)/n ) correctly calculates the nth root of p

New poster
Posts: 6
Joined: Mon Sep 15, 2003 3:21 am
Location: Charleston, S.C.
Contact:
Try the formula:
a log b = log b / log a
Maybe my math skills are a little rusty, but I thought the formula was

a log b = log (b^a)

and for the compiler warnings (Visual C++ doesn't have any problem with that,) the problem statement guarantees k to be less than 1E9. i used double for the precision in the log statement, and then since it is guaranteed by problem statement to fit in long, i did the basic round-and-convert. i also tried submitting the answer as a double with the ios::showpoint flag off, but no dice.

thanks for the replies...although i haven't had any problems previously either copy and pasting or uploading the code from visual, could that be a problem?

thanks again
"Moral victories are for girls!" -- Shawn Kiernan

"You can't spell geek without EE..." -- Larkin Gentry

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Yes, a log b equals log(b^a). That's why I added some note since I don't know how to type 'a' in superscript model. The 'a' in 'a log b' here doesn't mean a * log b, get it??
I recommend this formula since it's more precise.
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

New poster
Posts: 6
Joined: Mon Sep 15, 2003 3:21 am
Location: Charleston, S.C.
Contact:
Ok I'm sorry but I'm still having some problems understanding that formula. i think i understand it now to mean

a log(a) b = log(a) b / log(a) a

where the a in parenthesis means log(base a) of.
PS: a in a log b is the base of the log
so using natural logs, it seems that the formula would be

e ln b = ln b / ln e --> e ln b = ln b

can you tell me where i'm going wrong? and even after that, i'm unclear on how to express p=k^n in the form ln b / ln a:

ln p = ln k^n --> ln p = n ln k --> 1/n = ln k / ln p -->(by blind app of formula) --> 1/n = p ln k

sorry, i have been out of school for a while..
"Moral victories are for girls!" -- Shawn Kiernan

"You can't spell geek without EE..." -- Larkin Gentry

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Sorry, I got the problem wrong!
shamim is right. use pow() function :
pow(p,1/n);
Good luck!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

113 - Why Wrong Answer? :'(

This is my code.

k = 10^(log10(p)/n);
[c]

/*
Power Criptography
problem: 113
*/
# include <stdio.h>
# include <math.h>
# include <string.h>

main(){
int n,val,c,i;
double x;
int k;
char p[200];
while(scanf("%d\n",&k) != EOF){
gets(p);
n = strlen(p);
c = 100;
val = 0;
for(i = 0; i<4;i++ , c /=10){
if(p == NULL) break;
val += (p-'0')*c;
}
x = log10((double)val);
x = x-3+n;
x /= k;
printf("%.0lf\n",pow(10,x));
}
return 0;
}[/c]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
[cpp]char p[200];
while(scanf("%d\n",&k) != EOF){
gets(p);
[/cpp]

The given numbers will actually fit in the double data type, so there is no need to consider string. [/b]

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Why don't you use pow(p,1/n);

Sensor
New poster
Posts: 4
Joined: Tue Nov 18, 2003 10:01 pm

Power of Cryptography (#113)

I have a problem:
It seems to be OK but I got WA??? I can't find error!
Can somebody help me?

{@BEGIN_OF_SOURCE_CODE}
{ @JUDGE_ID: XXX 113 Pascal}
program proga;
var datan,datap:string;

procedure nsqrt(ns,ps:string);
var n,p,ost,res:integer;
code,v:integer;
begin
val(ns,n,code);
v:=(length(ps) div n)+1;
ost:=length(ps)-v;
if ost>0 then
begin
val(copy(ps,1,v),p,code);
res:=round(exp(1/n*(ln(p)+ost*ln(10))));
end else
begin
val(ps,p,code);
res:=round(exp(1/n*(ln(p))));
end;
writeln(res);
end;

begin
while not eof(input) do
begin
nsqrt(datan,datap);
end;
end.
{@END_OF_SOURCE_CODE}

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

&#65283;113 why compile error???pliz help

[c]
#include<stdio.h>
#include<math.h>
#include<conio.h>
void main(void)
{
long n,p,loop;
while(scanf("%ld\n%ld",&n,&p)==2)
{
for(loop=1;loop<=p;loop++)
{
if((long)(pow(n,loop))==p)
{
printf("%ld\n",loop);
break;
}
}
}
}[/c]
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
don't use conio.h
it will produce compile error

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
yeah,i got it.thanks:)
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
From your stats, it looks like that you have 39 posts (experienced) and still you don't know that 'conio.h' gives a compile error. Very Strange!!!