## 10179 - Irreducible Basic Fractions

Moderator: Board moderators

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

### 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

Sherman MXF
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.   wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
i GUESS it should be 1. as 0/1 is irreducible

have you heard about phi function? where phi(n) = number of integers less than n and relatively prime to n. so an irreducible fraction p/n is just p, n relatively prime. so, get phi(n), u're close to the answer.

Sherman MXF
New poster
Posts: 14
Joined: Sun May 26, 2002 1:54 pm
Location: China
Thank you very much! I got ACCEPTED!   xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

### 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;
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:=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;
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
if (i=0) then break;
writeln(totient(i));
until false;
end.
[/pascal]
Can anybody spot my blind spot?

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:

### 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
Last edited by Subeen on Sun Oct 19, 2003 10:38 pm, edited 1 time in total.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

### Re: worng ans!!!

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
what should you output if n == 1 ....

and you needn't use double...

n = p1^e1 * p2^e2 *... * pk^ek

n must be divide by p1, p2, ... pk

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

### 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 * (1-1/p1) * (1/1-p2) * ... , where p1, p2, ... are prime divisors of n.
But it is too slow....
Any better way?

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
Maybe you can do some memorize(memorize the answer that less than 100000 or 1000000).
As you now, phi(p * q) = phi(p) * phi(q), p & q are prime numbers.
But I think it improves little.

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### 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 n-1, 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?

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.

abiczo
New poster
Posts: 7
Joined: Sat Apr 06, 2002 2:00 am
Location: Hungary

### 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^(k-1) 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

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
I also get Accepted for problem 10299 but p10179.
Can anyone provide some sample I/O?

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland
I had similar problem, but I had 10179 Acc and 10299 WA.
And I found the difference. In 10179 for 1 you should output 1 and in 10299 you should output 0;

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Contact:

### 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?????
From 0 to 0

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Why the difference

I would like to know, why the difference has ocuured.
Mathematically which one is valid.