CFR 795 G. Perfectionist Arkadiy ( Math )

題意：
給 A, H, W，代表有一個紙張 H * W 大小，圖片是一個邊長為 A 的正方形。現在要放任意個正方形，使得所有相鄰正方形之間，以及邊界和其相鄰的正方形的間距為任意實數 x。問 x 最小可以是多少，無解則輸出 -1。

制約：
The first line contains three integers a, h and w (1 ≤ a, h, w ≤ 1e9) — the size of photos and the height and the width of the wall.

解法：
假設最佳解圖片的擺放是 r 行 c 列。
那麼有 H = r * A + ( r + 1 ) * x。
因此為求方便考慮 H' = H + A = ( r + 1 ) * ( x + A )，W' = W + A = ( c + 1 ) * ( x + A )。
注意到 r 和 c 都必須是正整數：
令 g = gcd( H', W' )，p * g = H', q * g = W'，則 ( r + 1 ) : ( c + 1 ) = p : q。
用無條件捨去除法得到適當的最大的基數 k，就可以知道 ( r + 1 ) = k * p，( c + 1 ) = k * g。

時間 / 空間複雜度：
O( lg N )

#include <bits/stdc++.h>
using namespace std;

signed main() {
	int A, H, W;
	cin >> A >> H >> W;
	int g = __gcd( H + A, W + A );
	int p = ( H + A ) / g, q = ( W + A ) / g;
	int k = min( ( H + A ) / A / p, ( W + A ) / A / q );
	int r = k * p - 1, c = k * q - 1;
	if( r >= 1 and c >= 1 ) {
	  cout << fixed << setprecision( 7 ) << ( H - 1.0 * A * r ) / ( r + 1 ) << endl;
	} else {
		cout << -1 << endl;
	}
	return 0;
}