• <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)  編輯 收藏 引用 所屬分類: 解題報告

            久久久久亚洲精品无码蜜桃| 热RE99久久精品国产66热| 亚洲精品乱码久久久久久久久久久久 | 国产综合久久久久| 欧美日韩中文字幕久久伊人| 人妻少妇精品久久| 99久久无码一区人妻a黑| 久久久不卡国产精品一区二区| 久久午夜夜伦鲁鲁片免费无码影视 | 欧美精品福利视频一区二区三区久久久精品 | 国产精品久久婷婷六月丁香| 人妻精品久久久久中文字幕69| 97精品伊人久久大香线蕉app| 日日狠狠久久偷偷色综合96蜜桃 | 7777久久亚洲中文字幕| 亚洲国产成人精品91久久久| 精品久久人妻av中文字幕| 久久夜色撩人精品国产小说| 狠狠色婷婷综合天天久久丁香| 亚洲国产视频久久| 久久99热这里只有精品国产| 精品国产一区二区三区久久久狼 | 久久亚洲高清观看| 伊人久久久AV老熟妇色| 韩国三级中文字幕hd久久精品| 久久国产色AV免费看| 久久精品国产久精国产一老狼| 久久精品成人免费国产片小草| 国产精品久久久久影院嫩草| 伊人久久大香线蕉亚洲| 婷婷久久综合九色综合绿巨人| 狠狠精品干练久久久无码中文字幕 | 久久久久国产一级毛片高清板| 91精品国产91热久久久久福利| 亚洲国产一成人久久精品| 99久久精品国产一区二区 | 亚洲狠狠婷婷综合久久蜜芽| 伊人久久大香线蕉精品不卡| 久久精品国产一区二区三区不卡| 久久久久99精品成人片| 欧美精品一区二区久久|