• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Why so serious? --[NKU]schindlerlee

            2009年11月25日星期三.sgu106

            2009年11月25日星期三.sgu106
            這題終于過了......
            太容易錯了
            忘了sgu是ms win,用%lld錯了十幾次,干脆cin就得了,I64d在linux又編譯不了

            106. The equation

            There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how
            many integer roots of this equation are satisfy to the following conditions :
            x1<=x<=x2,   y1<=y<=y2. Integer root of this equation is a pair of integer numbers
            (x,y).

            Input
            Input contains integer numbers a,b,c,x1,x2,y1,y2 delimited by spaces and line breaks.
            All numbers are not greater than 108 by absolute value.

            Output
            Write answer to the output.

            Sample Input
            1 1 -3
            0 4
            0 4
            Sample Output
            4

            首先在開始正式講解之前我要說,原來除法不一定是下取整的。。。。
            比如 1 / 2 = 0
            但是-1 / 2 = 0;

            所以我們要自己寫上取整和下取整的函數
            看到zzy的一個寫法,很不錯,見代碼中的upper和lower

            直線可以寫成參數方程的模式
            L1: p0 + t * v; t為實數,v 為直線的方向向量

            ax + by + c = 0;
            首先可以把c移到右邊
            ax + by = -c;
            知道a,b可以利用擴展歐幾里德公式求出p0和d,(d = gcd(a,b))
            如果c不能整除d的話就沒有整數解,這點是顯然的,可以簡單思考一下.

            另外通過直線的幾何意義可以知道
            v = (b ,-a)或
            v = (-b, a)
            取其中一個即可
            tx = (x - x0)/b;
            ty = (y - y0)/-a;

            通過兩個去見求出tmin,tmax,之后
            ans = tmax - tmin + 1就是結果,如果ans < 0 就是無解

            此題破例貼代碼
             1 
             2 LL ans = 0;
             3 LL kmin = -300000000000000000LL, kmax = 300000000000000000LL;
             4 
             5 LL ext_gcd(LL a, LL b, LL & x, LL & y)
             6 {
             7     if (b == 0) {
             8         x = 1;
             9         y = 0;
            10         return a;
            11     } else {
            12         LL d = ext_gcd(b, a % b, x, y);
            13         LL t = x;
            14         x = y;
            15         y = t - a / b * y;
            16         return d;
            17     }
            18 }
            19 
            20 LL upper(LL a, LL b)
            21 {
            22     if (a <= 0)
            23         return a / b;;
            24     return (a - 1/ b + 1;
            25 }
            26 
            27 LL lower(LL a, LL b)
            28 {
            29     if (a >= 0)
            30         return a / b;
            31     return (a + 1/ b - 1;
            32 }
            33 
            34 void update(LL L, LL R, LL a)
            35 {
            36     if (a < 0) {
            37         L = -L;
            38         R = -R;
            39         a = -a;
            40         swap(L, R);
            41     }
            42     kmin = max(kmin, upper(L, a));
            43     kmax = min(kmax, lower(R, a));
            44 }
            45 
            46 int main()
            47 {
            48     LL a, b, c, x1, x2, y1, y2, x0, y0;
            49     cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2; // sgu 是ms win,應該用%I64d,我錯了20幾次才發現.
            50     c = -c,ans = 0;
            51     if (a == 0 && b == 0) {
            52         if (c == 0)
            53             ans = (LL) (x2 - x1 + 1* (y2 - y1 + 1);
            54     } else if (a == 0) {
            55         LL t = c / b;
            56         ans = (c % b == 0 && t <= y2 && t >= y1) * (x2 - x1 + 1);
            57     } else if (b == 0) {
            58         LL t = c / a;
            59         ans = (c % a == 0 && t <= x2 && t >= x1) * (y2 - y1 + 1);
            60     } else {
            61         LL d = ext_gcd(a, b, x0, y0);
            62         if (c % d == 0) {
            63             LL p = c / d;
            64             update(x1 - p * x0, x2 - p * x0, b / d);
            65             update(y1 - p * y0, y2 - p * y0, -/ d);
            66             ans = kmax - kmin + 1;
            67             if (ans < 0) ans = 0;
            68         }
            69     }
            70     cout << ans << endl;
            71     return 0;
            72 }
            73 
            74 


            posted on 2009-11-25 22:10 schindlerlee 閱讀(1379) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久精品国产久精国产思思| 国产一区二区精品久久岳| 中文成人久久久久影院免费观看| 久久久精品久久久久特色影视| 久久久精品视频免费观看| 久久久久se色偷偷亚洲精品av| 99精品国产99久久久久久97 | 久久精品国产91久久麻豆自制| 日本免费久久久久久久网站| 久久影视国产亚洲| 国产成人久久精品一区二区三区| 精品国产婷婷久久久| 亚洲精品无码久久久久去q| 青青草国产精品久久| 亚洲伊人久久成综合人影院| 久久久久人妻精品一区二区三区| 久久99精品免费一区二区| 色妞色综合久久夜夜| 色欲综合久久躁天天躁| 狠狠色丁香婷综合久久| 国产精品亚洲综合久久| 国产精品欧美久久久久天天影视| 亚洲AV日韩AV永久无码久久| 日韩久久久久中文字幕人妻| 天天综合久久久网| 韩国三级大全久久网站| 亚洲AV无码一区东京热久久| 国内精品伊人久久久久妇| 久久亚洲精品无码播放| 国内精品伊人久久久久影院对白| 久久久久亚洲av无码专区喷水| 国产成年无码久久久免费| 久久亚洲日韩看片无码| 亚洲AⅤ优女AV综合久久久| 久久精品亚洲男人的天堂| 亚洲狠狠久久综合一区77777| 精品久久香蕉国产线看观看亚洲| 日韩精品久久久肉伦网站| 亚洲午夜久久久久妓女影院 | 久久亚洲天堂| 久久亚洲中文字幕精品一区四|