var
m,i,n,n1:longint;

function nod(a,b:longint):longint;
{...}
end;


begin
readln(n);
n1:=(n-1) div 2;
m:=0;
for i:=1 to n1 do
  if nod(i,n)=1 then inc(m);
writeln(m);
end.

Thanks

i did the problem like u suggested:) and i got accepted but i dont really understand why is it like that..can u please explain me?

Edited by author 18.02.2005 17:12

Edited by author 18.02.2005 17:12

//
below I use divisibility by a real (not integer) number - hope that doesn't cause any confusions
//

Let us denote beta = Pi - alpha (from problem statement)

You can easily prove that the process described in the problem statement means that we simply fix the initial point on a circle, and then jump around with angle beta.

So now for given N you need to find the number of solutions for the following equalty:

N * beta mod 2Pi = 0, such that N is minimal

Obviously, beta must be p / N * Pi, where p is integer (elseway N * beta can't be divisible by 2Pi).

But beta = Pi - alpha and 0 < alpha < Pi, so 0 < beta < Pi;
this means that 0 <= p < N. On the other hand, p must be even - if it's not, N * beta = N * p / N * Pi = p * Pi will not be divisible by 2Pi. So p = 2 * i.

So we have the following candidates for beta: 2 * i / N * Pi, where 0 <= i < N div 2 (because p < N).

The last thing to take care of is that there's no such K < N that K * beta is divisible by 2Pi:

K * 2 * i / N * Pi (not divisble by) 2Pi.

This means that K * i must not be divisible by N for any K < N; which means that i and N must be coprimes.

So the answer is number of coprimes of N that are smaller that N / 2. If A and N are coprimes, then (N-A) and N are coprimes too, so the answer is (number of coprimes of N that are smaller that N) / 2.

To calculate this number we can use Euler's formula instead of a bruteforce solution:

if N = a1^p1 * a2^p2 * .. * ak^pk, where all ai are different and all ai are primes, then number of coprimes smaller than N is

E(N) = (a1 - 1) * .. * (ak - 1)   *   a1 ^ (p1 - 1) * .. * ak ^ (pk - 1)

so the answer is E(N) / 2

Michael Rybak! Respect!

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}
ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n / 2; i++)
{
    if (gcd(i, n) == 1)
        ans++;
}