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

            久久强奷乱码老熟女网站| 久久综合香蕉国产蜜臀AV| 岛国搬运www久久| 久久人人爽人人爽人人片AV麻豆| 很黄很污的网站久久mimi色| 亚洲精品无码久久不卡| 亚洲国产精品久久久天堂| 国产亚洲综合久久系列| 亚洲国产成人久久精品动漫| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 久久精品国产99国产精品| 狠狠色丁香婷婷久久综合| 91精品国产高清91久久久久久| 久久涩综合| 91精品无码久久久久久五月天| 久久久久人妻一区二区三区| 国产精久久一区二区三区| 婷婷综合久久中文字幕蜜桃三电影 | 久久99国产精品久久99| 色综合久久天天综线观看| 九九久久99综合一区二区| 亚洲第一极品精品无码久久| 免费一级欧美大片久久网| 国产情侣久久久久aⅴ免费| 亚洲第一永久AV网站久久精品男人的天堂AV| 无码精品久久久久久人妻中字| 久久激情五月丁香伊人| 亚洲国产精品久久久久| 久久天天躁夜夜躁狠狠| 伊人热热久久原色播放www| 国产精品久久久久久久午夜片 | 亚洲国产精品久久久天堂| 久久精品无码一区二区三区免费| 青青热久久综合网伊人| 久久精品国产99久久无毒不卡| 久久精品成人欧美大片| 亚州日韩精品专区久久久| 日本精品一区二区久久久| 久久久久国产一级毛片高清板| 久久精品中文字幕有码| 久久www免费人成看国产片|