CodeForces-16C: Monitor（GCD）

数论

Description

Reca company makes monitors, the most popular of their models is AB999 with the screen size $a × b$ centimeters. Because of some production peculiarities a screen parameters are integer numbers. Recently the screen sides ratio $x: y$ became popular with users. That's why the company wants to reduce monitor AB999 size so that its screen sides ratio becomes $x: y$, at the same time they want its total area to be maximal of all possible variants. Your task is to find the screen parameters of the reduced size model, or find out that such a reduction can't be performed.

Input
The first line of the input contains 4 integers — a, b, x and y $(1 ≤ a, b, x, y ≤ 2·10^9)$.

Output

If the answer exists, output 2 positive integers — screen parameters of the reduced size model. Output 0 0 otherwise.

Input

800 600 4 3
1920 1200 16 9
1 1 1 2

Output

800 600
1920 1080
0 0

题意： a和b是屏幕原来的尺寸，x和y是需要裁成的比例。要变成x：y的比例并且保证屏幕最大，输出这个最大的屏幕尺寸，如果不行就输出0。

分析：先把x和y这个比例约分，比如4:2就化成2:1，然后用a/x，b/y，取他们中的最小值，用这个最小值分别乘以最简的那个比例。

• 完整代码：

#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
LL gcd(LL a,LL b) //辗转相除法求最大公因数
{
    LL t;
    while(b)
    {
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}
int main()
{
    LL a,b,x,y,s;
    while(scanf("%lld%lld%lld%lld",&a,&b,&x,&y)!=EOF)
    {
        s=gcd(x,y);
        x/=s,y/=s; //比例先约分，化成最简的
        s=min(a/x,b/y);
        x*=s;
        y*=s;
        printf("%lld %lld\n",x,y);
    }
    return 0;
}