• <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>
            隨筆 - 68  文章 - 57  trackbacks - 0
            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆分類(74)

            隨筆檔案(68)

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

              是個經典問題了,求滿足a ^ 2 + b ^ 2 = c ^ 2且a、b、c兩兩互質的三元組個數,其中a、b、c都小于等于n,同時還要求出n以內不屬于三元組(不必互質)的數的個數,其中n <= 1000000。
              數據范圍很大,單純的n ^ 2的枚舉肯定是不行的。我發現互質的三元組不多,想找一個辦法求出互質的,然后篩出其他的三元組(乘以倍數),但是仍然想不出怎樣很快找到互質的三元組。到網上查了一下,找到了一個很好的網站(http://xserve.math.nctu.edu.tw/people/cpai/carnival/fraction/05.htm)講解這個問題。
              首先只需找到互質的a和b就可以了,其余的可以通過乘以一定的倍數得到。首先a和b必須不能都是奇數,否則的話,不妨設a = 2p + 1, b = 2q + 1, c = 2r。帶入a ^ 2 + b ^ 2 = c ^ 2有:2 * (r ^ 2 - p ^ 2 - q ^ 2 - p - q) = 1,出現了矛盾。這樣必然a和b一奇一偶,設a是偶數。恒等變換一下:(這里是x ^ 2 + y ^ 2 = z ^ 2,x是偶數)


              令u = (z - y) / 2,v = (z + y) / 2。因為y、z互質,那么u、v互質。如果不互質,有v = ku,變換后得到:z / y = (k + 1) / (k - 1)。因為z和y互質,這樣這個等式的解只能是z = k + 1且y = k - 1。這樣的話u = 1。可以理解為這也是互質的特殊情況(gcd = 1)。這樣(x / 2) ^ 2 = u * v,u和v沒有公共的質因數,因此必然u和v都是完全平方數。接下來的事情就比較簡單了,令u = m ^ 2,v = n ^ 2,然后利用m和n表示x、y、z有:y = n ^ 2 - m ^ 2,x = 2 * m * n,z = n ^ 2 + m ^ 2。這樣題目中數據范圍1000000,而枚舉m和n的范圍最大1000,這個復雜度就可以接受了。枚舉的時候不用擔心出現重復的互質的x與y,因為這里x一定是偶數,如果x和y已經互質,那么y一定是奇數,解是唯一的。
              很囧的是這個巧妙的方法居然公元前250年就有大牛想到了(丟番圖),實在orz!

             

            posted on 2009-06-09 09:09 sdfond 閱讀(344) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm - Number Theory
            久久人人青草97香蕉| 色偷偷偷久久伊人大杳蕉| 久久精品国产第一区二区| 久久精品国产亚洲αv忘忧草 | 久久久WWW成人免费精品| 久久夜色精品国产亚洲| 国产成人精品久久免费动漫| 久久久久97国产精华液好用吗| 国产成人无码精品久久久性色| 91久久精品国产免费直播| 久久国产色av免费看| 久久久WWW成人免费毛片| 69国产成人综合久久精品| 久久久久亚洲AV成人网| 97久久久久人妻精品专区| 2020久久精品亚洲热综合一本| 日韩欧美亚洲综合久久影院d3| 久久久一本精品99久久精品88| 99久久无码一区人妻| 人妻少妇久久中文字幕 | 亚洲熟妇无码另类久久久| 久久国产精品一区| 91久久精品视频| 欧美综合天天夜夜久久| 无码人妻精品一区二区三区久久久| 久久精品国产亚洲网站| 蜜臀av性久久久久蜜臀aⅴ麻豆| 精品多毛少妇人妻AV免费久久 | 91精品国产色综久久| 日本WV一本一道久久香蕉| 人妻精品久久久久中文字幕69 | 色偷偷91久久综合噜噜噜噜| 国产精品视频久久久| 国内精品久久久久影院老司| 久久久久99精品成人片试看| 精品伊人久久大线蕉色首页| 久久婷婷五月综合成人D啪| 免费观看久久精彩视频| 色欲久久久天天天综合网精品| 国内精品免费久久影院| 97精品国产91久久久久久|