UVA 12493 Stars

Maratona de Programação da SBC – ACM ICPC – 2012                                                          

                                               Problem L

                                                 Stars

   Fernando  won  a  compass  for  his  birthday,  and  now  his  favorite  hobby  is  drawing  stars: first,  he

marks N points on a circumference, dividing it into N equal arcs; then, he connects each point to the

kth next point, until returning to the first point.

   Depending on the value of k, Fernando may or may not reach all points marked on the circumference;

when that happens, the star is called  complete.  For example, when N = 8, the possible stars are shown

in the figure below.  Stars (a) and (c) are complete, while stars (b) and (d) are not.

   Depending on the value of N, it may be possible to draw many different stars; Fernando asked you

to write a program that, given N, determines the number of complete stars he can draw.

Input

   The  input  contains  several  test  cases. Each  test  case  contains  a  single  line,  containing  a  single

integer N, indicating the number of arcs in which the circumference was divided.

Output

   For each test case, your program must print a single line containing a single integer, indicating the

number of complete stars that can be drawn.

Restrictions

   3 ≤ N < 231

Example

    Sample input                              Sample output

    3                                                  1

    4                                                  1

    5                                                  2

    18                                                3

    36                                                6

    360                                             48

    2147483647                            1073741823

题意：给一个圆，用N个点将圆平均分成N个部分，以某点为起点，连结接下去的第k个点，直到回到原点，求能画出多少个complete stars ，complete stars：通过上述方法，最终每个点都连接到的图，称为complete stars 。

思路：分析可知，题目所求为1~N中，与N互质的数的个数，但因为有相同的complete stars 因此必须除掉。

#include<stdio.h>
#include<math.h>
int eular(int n)
{
    int ret=1,i;
    for(i=2;i<=sqrt(n)+1;i++)
        if(n%i==0)
        {      
     n=n/i;
     ret*=(i-1);
            while(n%i==0)
            {
                n/=i;
                ret*=i;
            }
        }
    if(n>1)
        ret*=(n-1);
    return ret;
}
int main()
{
  int t,a,j;
  while(scanf("%d",&a)!=EOF)
  {
               t=eular(a);
    t=t/2;
    printf("%d\n",t);
  }
  return 0;
}