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

            Climber.pI的OI之路

            Through the darkest dark,may we see the light.

            NOIP 2001 最大公約數和最小公倍數問題

            很有趣的一個數學問題,這一周看完《背包九講》后,就開始看CCF出的NOIP2001-2003的題解.之前認為很水的題目的最優算法相當精妙,這進一步認證了僅僅AC是不夠的,還需要進一步研究算法.

            題意略.需要注意的是,題目僅僅需要求出符合條件的數對的個數,而非答案.
            因而,我們可以利用一些數學分析得到一個非常簡潔的結論:
            以x0,y0分別為最大公約數和最大公倍數的數對個數為2^n,n是y0/x0的不同質因子個數.

             

             1#include<stdio.h>
             2int main()
             3{
             4  int x0, y0, x, i = 2, k = 0;
             5  scanf(“%d%d”, &x0, &y0);
             6  if (y0 % x0 != 0{printf(“0\n”); return 0;}
             7  x = y0 / x0;
             8  while (x != 1)
             9  {
            10    while (x % i != 0) i++; k++;
            11    while (x % i == 0) x /= i;
            12  }

            13  printf(“%d\n”, 1<<(k));
            14}

            posted on 2010-09-11 22:10 Climber.pI 閱讀(1802) 評論(1)  編輯 收藏 引用 所屬分類: 數學

            Feedback

            # re: NOIP 2001 最大公約數和最小公倍數問題 2013-11-03 16:18

            的   回復  更多評論   

            久久久中文字幕| 久久久久高潮毛片免费全部播放| 久久国产精品99久久久久久老狼| 一本色道久久88精品综合| 91麻豆国产精品91久久久| 久久久久高潮毛片免费全部播放 | 狠狠人妻久久久久久综合| 国产精品99久久久久久猫咪| 久久综合久久伊人| 精品国产乱码久久久久软件 | 国产毛片欧美毛片久久久| 国产精品久久久久久久| 亚洲人成电影网站久久| 99久久免费国产精精品| 久久青青色综合| 99久久国产亚洲高清观看2024| 国产精品久久久久久久久久影院| 久久国产色AV免费观看| 色妞色综合久久夜夜| 国产精品伊人久久伊人电影| 日产精品久久久一区二区| 久久国产AVJUST麻豆| 国产午夜精品久久久久九九| 久久久久久国产精品免费无码 | 青青草原综合久久大伊人精品| 亚洲精品国产综合久久一线| 93精91精品国产综合久久香蕉| 亚洲中文字幕无码久久综合网 | 久久亚洲中文字幕精品有坂深雪| 色综合久久中文色婷婷| 国产成人精品久久二区二区| 亚洲AV无码久久精品色欲| 色综合久久夜色精品国产| 亚洲国产成人精品女人久久久| 99久久精品免费观看国产| 久久777国产线看观看精品| 国产精品久久久久久久久鸭| 精品熟女少妇a∨免费久久| 久久精品国产亚洲AV无码偷窥| 久久精品天天中文字幕人妻| 色诱久久久久综合网ywww|