10179 - Irreducible Basic Fractions

[sjn]

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]

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]

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]

Thank you very much! I got ACCEPTED!

[xenon]

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?

[Subeen]

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

[Even]

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]

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]

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]

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?

thanx in advance.

PS: I just realized that all references to me except for the first one refer to the program not me - sorry :)

[abiczo]

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]

I also get Accepted for problem 10299 but p10179.
Can anyone provide some sample I/O?

[szymcio2001]

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]

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

[shamim]

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