toj_2918.cpp

Tianjin University Online Judge 的80多道题目 .

/*2918.   LCM Revisited Time Limit: 5.0 Seconds   Memory Limit: 65536K
Total Runs: 2   Accepted Runs: 2
Case Time Limit: 1.0 Seconds


All of you know about LCM (Least Common Multiple). For example LCM of 4 and 6 is 12. We need to find the number of such m that 1 ≤ m ≤ n, for every m LCM (m, n)> n and LCM (m, n) < m*n.

For example if n=6, then for every m (1≤m≤6) LCM (1, 6) = 6, LCM (2, 6) =6, LCM (3, 6) = 6, LCM (4, 6) = 12, LCM (5, 6) = 30, LCM (6, 6) = 6. So here only one number 4 have a LCM (4, 6) = 12 in the range 6< LCM (4, 6) <24. So the answer will be 1.
Input

Each line contains one nonzero positive integer n (0 < n < 2^31). Last line will contain zero indicating the end of input. This line should not be processed. You will need to process maximum 1000 lines of input.

Output

For each line of input, print the number of m.
Sample Input

1
6
5
12
0

Sample Output

0
1
0
3

Problem Setter: Kreshano Dutta


Source: CUET individual contest*/
#include<cstdio>

int &gcd( int & n , int &i )
{
  int static a , b;
  int static temp;
  a =n;
  b = i;
  while ( b != 0 )
    {
      temp = a;
      a = b;
      b = temp % b;
    }
  return a;
}
  
int main()
{
  int i , m , n , result;
  while ( scanf( "%d" , &n ) != EOF && n != 0 )
    {
      result = 0;
      for ( i = 2; i < n; i++ )
	{
	  //	  printf( "gcd( %d , %d ) = %d\n" , n , i , gcd( n , i ) );
	  if ( n % i != 0 && gcd( n , i ) != 1 )
	    result++;
	}
      printf( "%d\n" , result );
    }
  return 0;
}