關於部落格
聊盡天南地北,無所不聊
  • 58620

    累積人氣

  • 1

    今日人氣

    2

    追蹤人氣

ACM 294

ACM 294:Divisors /* 問題簡述:寫一個程式找出在這個範圍內的數,哪一個數有最多的除數(就是小於等於這個數,且可以被這個數除盡的數。例如:6有4個除數,分別是1,2,3,6 */ /* 輸入檔案:輸入的第一列有一個正整數N,代表以下有幾組測試資料。每組測試資料一列,含有2個正整數L,U,代表某一範圍的數中最小及最大的數。 並且 1 < = L <= U <= 1000000000,0 <= U-L <= 10000 */ /* 輸出檔案:對每一組測試資料,找出在範圍內有最多除數的數P,以及他有多少個除數D。然後依這樣的格式輸出:'Between L and H, P has a maximum of D divisors. */ /***************************************************************/ #include<stdio.h> #include<stdlib.h> #include<math.h> //有使用到sqrt int max(int); int main() { int times; scanf("%d",&times);     //輸入次數 while (times--) { int big,small,change; int i,j,compare=0; int arr[2]={0};    //設立存某值 跟某值的最大除數 scanf("%d",&small);   //輸入L scanf("%d",&big);    //輸入U for (i=small;i<=big;i++)   //i值介於U跟L { compare=max(i);   //找出最大除數值 if (compare>arr[1])   //假如大於儲存最大除數值 { arr[1]=compare;   //則互換 arr[0]=i;    //儲存某值 則變成i } } printf("Between %d and %d, %d has a maximum of %d divisors.n",small,big,arr[0],arr[1]); } return 0; } int max(int i)    //尋找最大除數 { int j,c=0; for (j=1;j<=sqrt(i);j++)   //只需要找到開根號的i { if (i%j==0){    //可整除 if(j*j!=i)    //用因數對稱性,去判斷 c+=2;    //如果不等於,則+2 else c++;    //假如等於,則表示j^2==i 因數只有一個 } } return c;    //回傳c } /************************************************************/ /* 解題想法(演算法): int max(int i)    //尋找最大除數 { int j,c=0; for (j=1;j<=sqrt(i);j++)   //只需要找到開根號的i { if (i%j==0){   //可整除 if(j*j!=i)   //用因數對稱性,去判斷 c+=2;   //如果不等於,則+2 else c++;    //假如等於,則表示j^2==i 因數只有一個 } } return c;    //回傳c } 要找因數的話,只要從1找到i值的開根號即可,因應因數都有對稱性 設a*b=c a就是有另一個相對應的因數b, 因此只要找到a就可以知道有另一個數也是c的因數 所以只要找到開根號i,除非是完全平方數,j^2==i 只能加1,因為因數是一樣的 */ /************************************************************/ /* 測試項目: */ /* 1. 輸入:1 999999900 1000000000 輸出:Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.   */ /************************************************************/
相簿設定
標籤設定
相簿狀態