toj_2916.cpp

来自「Tianjin University Online Judge 的80多道题目 」· C++ 代码 · 共 56 行

/*2916.   Help Me Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 10   Accepted Runs: 3


We all interested in mathematics and world are divided in to two parts. One who are interested in mathematics and other who are afraid of mathematics.
Here is a equation:
      ( X * N ) % Y = 0

Given two number X & Y you have to find minimum N that satisfies the equation.
Input:

Input consists of two positive integer X & Y . (1≤X,Y≤2000000000)
Output:

You have to output minimum N.
Sample Input:

1 5
6 7

Sample Output:

5
7

Problem Idea: M.H. Rasel.
Problem Setter: Md. Shakil Ahmed.


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

int gcd( int a , int b )
{
  int static  temp;
  while ( b != 0 )
    {
      temp = a;
      a = b;
      b = temp % b;
    }
  return a;
}
      
  
int main()
{
  int x , y , n;
  while ( scanf( "%d%d" , &x , &y ) != EOF )
    {
      n = y / gcd( x , y );
      printf( "%d\n" , n);
    }
  return 0;
}