• <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
            這題終于過了......
            太容易錯(cuò)了
            忘了sgu是ms win,用%lld錯(cuò)了十幾次,干脆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的一個(gè)寫法,很不錯(cuò),見代碼中的upper和lower

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

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

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

            通過兩個(gè)去見求出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,我錯(cuò)了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) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告

            久久亚洲精品成人AV| 国产精品9999久久久久| 99久久免费只有精品国产| 久久久WWW免费人成精品| 亚洲色欲久久久久综合网 | 国产成人久久精品麻豆一区| 无码任你躁久久久久久老妇App| 99久久久精品| 无码专区久久综合久中文字幕 | 亚洲乱码精品久久久久..| 久久久久人妻精品一区| 亚洲欧洲中文日韩久久AV乱码| 中文无码久久精品| 国产精品乱码久久久久久软件 | 久久久精品视频免费观看| 国产成人久久精品一区二区三区| 国产成人精品久久一区二区三区 | 国产A级毛片久久久精品毛片| 2021国内久久精品| 狠狠精品久久久无码中文字幕| 久久夜色tv网站| 伊人久久大香线蕉影院95| 久久青青草视频| 少妇熟女久久综合网色欲| 大香网伊人久久综合网2020| 久久发布国产伦子伦精品| 久久综合亚洲鲁鲁五月天| 久久涩综合| 日产精品久久久久久久性色| 亚洲国产成人精品91久久久| 波多野结衣久久精品| 日本精品久久久久影院日本| 99久久国产热无码精品免费久久久久| 久久久久久久久无码精品亚洲日韩| 欧美精品九九99久久在观看| 色偷偷91久久综合噜噜噜噜| 久久九九久精品国产| 久久综合九色综合欧美就去吻| 久久国产午夜精品一区二区三区| 国产亚洲色婷婷久久99精品91| 丰满少妇人妻久久久久久4|