10179  Irreducible Basic Fractions
Moderator: Board moderators
10179  Irreducible Basic Fractions
i have passed p10229
but i can't pass p10179 with the code of p10229, why
the judge returned 'runtime error' why?
thx
but i can't pass p10179 with the code of p10229, why
the judge returned 'runtime error' why?
thx

 New poster
 Posts: 14
 Joined: Sun May 26, 2002 1:54 pm
 Location: China
10179
What should i print for 1?
0 or 1?
Do you have any fast algorithm to solve it in 4 seconds?
I precalculated a prime table, but i got WA.
0 or 1?
Do you have any fast algorithm to solve it in 4 seconds?
I precalculated a prime table, but i got WA.

 New poster
 Posts: 14
 Joined: Sun May 26, 2002 1:54 pm
 Location: China
same problem
I have the same problem, altough my code gets a WA, not a RTE.
The following program works fine with 10299, but gets WA for 10179.
[pascal]var
prime:array[1..3410] of integer;
function is_prime(i:integer):boolean;
var
p,j:integer;
b:boolean;
begin
j:=1;
p:=prime[1];
b:=true;
while (p*p<=i) do begin
if ((i mod p)=0) then begin
b:=false;
break;
end;
inc(j);
p:=prime[j];
end;
is_prime:=b;
end;
procedure init_primes;
var
i,p:integer;
begin
p:=1;
prime[1]:=2;
i:=3;
while (i<31623) do begin
if is_prime(i) then begin
inc(p);
prime[p]:=i;
end;
i:=i+2;
end;
end;
function divisor(i:integer):integer;
var
p,j:integer;
b:boolean;
begin
j:=1;
p:=prime[1];
b:=true;
while (p*p<=i) do begin
if ((i mod p)=0) then begin
b:=false;
break;
end;
inc(j);
p:=prime[j];
end;
if not b then divisor:=p else divisor:=i;
end;
function totient(i:integer):integer;
var
t:longint;
j,d,dd:integer;
begin
t:=i;
j:=i;
dd:=1;
while (j>1) do begin
d:=divisor(j);
if (dd<>d) then begin
dd:=d;
t:=(t*(i(i div d))) div i;
end;
j:=j div d;
end;
totient:=t;
end;
var
i:integer;
begin
init_primes;
repeat
readln(i);
if (i=0) then break;
writeln(totient(i));
until false;
end.
[/pascal]
Can anybody spot my blind spot?
The following program works fine with 10299, but gets WA for 10179.
[pascal]var
prime:array[1..3410] of integer;
function is_prime(i:integer):boolean;
var
p,j:integer;
b:boolean;
begin
j:=1;
p:=prime[1];
b:=true;
while (p*p<=i) do begin
if ((i mod p)=0) then begin
b:=false;
break;
end;
inc(j);
p:=prime[j];
end;
is_prime:=b;
end;
procedure init_primes;
var
i,p:integer;
begin
p:=1;
prime[1]:=2;
i:=3;
while (i<31623) do begin
if is_prime(i) then begin
inc(p);
prime[p]:=i;
end;
i:=i+2;
end;
end;
function divisor(i:integer):integer;
var
p,j:integer;
b:boolean;
begin
j:=1;
p:=prime[1];
b:=true;
while (p*p<=i) do begin
if ((i mod p)=0) then begin
b:=false;
break;
end;
inc(j);
p:=prime[j];
end;
if not b then divisor:=p else divisor:=i;
end;
function totient(i:integer):integer;
var
t:longint;
j,d,dd:integer;
begin
t:=i;
j:=i;
dd:=1;
while (j>1) do begin
d:=divisor(j);
if (dd<>d) then begin
dd:=d;
t:=(t*(i(i div d))) div i;
end;
j:=j div d;
end;
totient:=t;
end;
var
i:integer;
begin
init_primes;
repeat
readln(i);
if (i=0) then break;
writeln(totient(i));
until false;
end.
[/pascal]
Can anybody spot my blind spot?
worng ans!!!
i used euler's phi function too, but i got W.A.
someone plz see what is wrong with my solution?
[c] code removed
[/c]
thankx got AC
someone plz see what is wrong with my solution?
[c] code removed
[/c]
thankx got AC
Last edited by Subeen on Sun Oct 19, 2003 10:38 pm, edited 1 time in total.
Re: worng ans!!!
what should you output if n == 1 ....Subeen wrote:i used euler's phi function too, but i got W.A.
someone plz see what is wrong with my solution?
[c]#include <stdio.h>
#include <math.h>
int isprime(long n)
{
int r = ceil(sqrt(n));
int i;
if(n==2) return 1;
if(!(n%2)) return 0;
for(i=3; i<=r; i+=2)
if(!(n%i)) return 0;
return 1;
}
void main()
{
long m, n;
double count;
long i, root;
while(scanf("%ld", &n) && n)
{
count = n;
root = ceil(sqrt(n));
for(i=2; i<root; i++)
if(!(n%i))
{
m = n / i;
if(isprime(i))
count *= (1.0  1.0 / (double)i);
if(isprime(m))
count *= (1.0  1.0 / (double)m);
}
if(!(n%root) && isprime(root))
count *= (1.0  1.0 / (double)root);
if(count==n) count;
printf("%.0lf\n", count);
}
}
[/c]
thankx
and you needn't use double...
n = p1^e1 * p2^e2 *... * pk^ek
n must be divide by p1, p2, ... pk
10179  Irreducible Basic Fractions
I know it asks to calculate phi(n) for given n, where phi(n) is Euler totient function. I know
phi(n) = n * (11/p1) * (1/1p2) * ... , where p1, p2, ... are prime divisors of n.
But it is too slow....
Any better way?
phi(n) = n * (11/p1) * (1/1p2) * ... , where p1, p2, ... are prime divisors of n.
But it is too slow....
Any better way?
10179  algorithm
I just would like to ask someone if I am going on the right track or not...
First I figure out if the denominator is prime or not. If it is, the output should be n1, right? (by the way, what should be the output for n=1? 0 or 1?)
Otherwise, I get all the primes, smaller than n^0.5, which divide n and store them. Then I go through a loop (answer=0,i=1;i<n;i++) and check if any of the stored primes is a divisor of n. If none of them, then answer++;
After the loop is over, I just print answer's value. The idea seemed right to me, I get good answers for input I come up with, except for the sample input 7654321, where I get 7251462 instead of 7251444. Is the idea wrong or is there should be some problem with the implementation?
thanx in advance.
PS: I just realized that all references to me except for the first one refer to the program not me  sorry :)
First I figure out if the denominator is prime or not. If it is, the output should be n1, right? (by the way, what should be the output for n=1? 0 or 1?)
Otherwise, I get all the primes, smaller than n^0.5, which divide n and store them. Then I go through a loop (answer=0,i=1;i<n;i++) and check if any of the stored primes is a divisor of n. If none of them, then answer++;
After the loop is over, I just print answer's value. The idea seemed right to me, I get good answers for input I come up with, except for the sample input 7654321, where I get 7251462 instead of 7251444. Is the idea wrong or is there should be some problem with the implementation?
thanx in advance.
PS: I just realized that all references to me except for the first one refer to the program not me  sorry :)
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Euler phi function
You should calculate Euler's phi function for the given input values.
Since phi is multiplicative it's easy to calculate it:
phi(n)=phi(p1^k1) * ... * phi(pl^kl) where n=p1^k1 * ... * pl^kl and p1, ..., pl are primes.
phi(p^k) = p^k  p^(k1) if p is prime.
For example: 12 = 2^2 * 3, phi(12) = phi(2^2) * phi(3)= 2 * 2 = 4
123456 = 2^6 * 3 * 643, phi(123456) = 32 * 2 * 642 = 41088
7654321 = 19 * 402859, phi(7654321) = 18 * 402858 = 7251444
Best regards,
Andras Biczo
Since phi is multiplicative it's easy to calculate it:
phi(n)=phi(p1^k1) * ... * phi(pl^kl) where n=p1^k1 * ... * pl^kl and p1, ..., pl are primes.
phi(p^k) = p^k  p^(k1) if p is prime.
For example: 12 = 2^2 * 3, phi(12) = phi(2^2) * phi(3)= 2 * 2 = 4
123456 = 2^6 * 3 * 643, phi(123456) = 32 * 2 * 642 = 41088
7654321 = 19 * 402859, phi(7654321) = 18 * 402858 = 7251444
Best regards,
Andras Biczo

 New poster
 Posts: 38
 Joined: Mon Dec 09, 2002 1:53 pm
 Location: Poznan, Poland
Re algorithm
A number can have a prime factor greater than its sqrt. It is the case with
the input 7654321. But I've the confusion about the input 1.Any idea?????
the input 7654321. But I've the confusion about the input 1.Any idea?????
From 0 to 0
Why the difference
I would like to know, why the difference has ocuured.
Mathematically which one is valid.
Mathematically which one is valid.