久久综合亚洲色HEZYO社区,麻豆成人久久精品二区三区免费 ,色综合久久久久久久久五月

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 的

的回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 轉:在博客園日志中顯示數學公式（舊，ASCIIMathML.js版說明）求導復習《同中學生談排列組合》蘇淳讀書札記 NOIP 2001 最大公約數和最小公倍數問題

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Climber.pI的OI之路

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

Feedback

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

導航

統計信息

News

常用鏈接

留言簿

隨筆分類

隨筆檔案

My Blog

搜索

最新評論

閱讀排行榜

評論排行榜