Обсуждение @ 1259. Как стать звездой @ Timus Online Judge

ace Accepted [2] // Задача 1259. Как стать звездой 20 окт 2012 11:51

ibra (TNU) interesting [2] // Задача 1259. Как стать звездой 19 май 2009 02:14

Muravev Slava [Samara SAU] Why WA6? // Задача 1259. Как стать звездой 3 янв 2011 17:42

Tigran Hakobyan Solution // Задача 1259. Как стать звездой 24 ноя 2010 23:42

Saturn (HUS) How to solve this problem?? [6] // Задача 1259. Как стать звездой 8 июл 2004 23:25

vano_B1 VERY SIMPLE PROBLEM [5] // Задача 1259. Как стать звездой 8 июл 2004 23:33

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.

Saturn (HUS) Re: VERY SIMPLE PROBLEM // Задача 1259. Как стать звездой 9 июл 2004 15:46

Thanks

The Big Bad Wolf (Cristina Stancu-Mara) why? [3] // Задача 1259. Как стать звездой 18 фев 2005 17:11

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

Michael_Rybak Re: why? [2] // Задача 1259. Как стать звездой 3 фев 2006 19:29

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

Sid Re: why? [1] // Задача 1259. Как стать звездой 3 фев 2006 22:09

Michael Rybak! Respect!

hhgff Re: why? // Задача 1259. Как стать звездой 4 июл 2010 20:15

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++;
}

Burmistrov Ivan (USU) I have in passing received values an alpha // Задача 1259. Как стать звездой 1 дек 2005 00:01

Algorithm How to slove 1259? Maths? [4] // Задача 1259. Как стать звездой 5 апр 2004 19:30

Обсуждение задачи 1259. Как стать звездой