OJ Board

i have passed p10229

but i can't pass p10179 with the code of p10229, why

the judge returned 'runtime error' why?

thx

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.

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.

Thank you very much! I got ACCEPTED!

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?

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

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

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?

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.

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 :)

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

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

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;

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

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