2011-06-01 22:39:59Morris

a097. PARKET

http://zerojudge.tw/ShowProblem?problemid=a097

內容 :

Ivica家的客廳地板最近正在整修,整個矩形地板面積長L英吋,寬W英吋.

而他家的正方形地磚則每一個大小剛好為1*1平方英吋,地磚顏色則有黑色及灰色兩種.

而在黑灰色千千萬萬種組合中,他決定選擇中間為一黑色矩形(總數R平方英吋)邊框則由灰色磚塊(總數B平方英吋)排列而成的圖案樣式.四面的邊框厚度需相同.

底下便是範例測資2的圖示-外層為灰色磚塊形成的邊框,內層則為2個黑色磚塊形成的矩形圖案:

picture for problem

有一天Marica去拜訪Ivica家.她邊吃著她的餅乾並數著各種顏色的磚塊數量.她回家時又想起了這B,R兩個數字並要你寫一個程式根據B,R的值算出Ivica家客廳地板的大小(L,W). 

輸入說明 :

本題包含多組測試資料,每組測資各占一行,包含B,R兩個整數(<=2^30). 

輸出說明 :

對於每組測資請輸出對應的L,W(L>=W)以空白分隔,若有多組L,W解請輸出L,W值相差最大的那組解.你可以假設對於每組輸入都必有一組或一組以上的L,W解 

範例輸入 :

8 1
10 2

範例輸出 :

3 3
4 3

提示 :

出處 :

SPOJ改 (管理:pcsh710742)

作法 : 暴力
硬拆吧,然後利用判別式找出整數解

/**********************************************************************************/
/*  Problem: a097 "PARKET" from SPOJ改                                           */
/*  Language: C                                                                   */
/*  Result: AC (2ms, 274KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-05-31 21:55:14                                     */
/**********************************************************************************/


#include<stdio.h>
#include<math.h>
main() {
    long long B, R, a, b, A, D, t;
    while(scanf("%lld %lld", &B, &R) == 2) {
        long long sq = (long long)sqrt(R);
        for(a = 1; a <= sq; a++) {
            if(R%a == 0) {
                b = R/a;
                A = a + b;
                D = 4 * (A*A + 4*B);
                t = (long long)sqrt(D);
                if(t * t == D && (-2*A + t)%8 ==0 ) {
                    printf("%lld %lld\n", b + (-2*A + t)/4, a + (-2*A + t)/4);
                    break;
                }
            }
        }
    }
    return 0;
}