• <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;

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

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

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

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

            通過兩個去見求出tmin,tmax,之后
            ans = tmax - tmin + 1就是結(jié)果,如果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,應(yīng)該用%I64d,我錯了20幾次才發(fā)現(xiàn).
            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 閱讀(1380) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            国产精品久久久久久久久久免费| 久久无码人妻一区二区三区| 日韩亚洲欧美久久久www综合网| 久久免费精品视频| 久久精品无码专区免费| 久久人与动人物a级毛片| 97久久婷婷五月综合色d啪蜜芽 | 色婷婷综合久久久久中文| 久久香综合精品久久伊人| 99久久精品这里只有精品 | 色欲久久久天天天综合网| 91久久精品91久久性色| 中文字幕精品无码久久久久久3D日动漫| 色天使久久综合网天天| 999久久久无码国产精品| 日本精品一区二区久久久| 欧美777精品久久久久网| 亚洲中文字幕无码久久精品1| 99久久夜色精品国产网站| 人妻精品久久无码专区精东影业| 精品国产热久久久福利| 无码伊人66久久大杳蕉网站谷歌| yellow中文字幕久久网| aaa级精品久久久国产片| 99精品国产99久久久久久97| 亚洲午夜无码AV毛片久久| 99热热久久这里只有精品68| 久久99国内精品自在现线| 性欧美丰满熟妇XXXX性久久久 | 久久综合久久久| 97久久精品无码一区二区天美| 精品一二三区久久aaa片| 一本久久a久久精品综合香蕉| 国产福利电影一区二区三区久久老子无码午夜伦不 | 亚洲伊人久久成综合人影院 | 久久精品aⅴ无码中文字字幕不卡 久久精品成人欧美大片 | 亚洲AV无码久久精品成人| 久久综合国产乱子伦精品免费| 亚洲午夜无码久久久久| 亚洲精品乱码久久久久久中文字幕 | 久久青青草原国产精品免费|