反素數

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6686????Accepted Submission(s): 4001
Problem Description 反素數就是滿足對于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子個數),則x為一個反素數。現在給你一個整數區間[a,b],請你求出該區間的x使g(x)最大。
Input 第一行輸入n,接下來n行測試數據
輸入包括a,b, 1<=a<=b<=5000,表示閉區間[a,b].
Output 輸出為一個整數,為該區間因子最多的數.如果滿足條件有多個,則輸出其中最小的數.
Sample Input 3 2 3 1 10 47 359 Sample Output 2 6 240 Hint 2的因子為：1 2 10的因子為:1 2 5 10 Source HDU 2008-10 Programming Contest

問題鏈接：HDU2521 反素數。

題意簡述：參見上文。

問題分析：

題目為反素數，實際上與素數似乎沒有關系，不過是一個定義而已。

關鍵是計算整數的因子個數，求區間的中的x使得g(x)即x的因子個數為最大。

程序說明：本程序采用ACM題最普通的套路，為避免重復計算就先打表。把功能封裝到函數中也是一種值得推薦的做法。

AC的C語言程序如下：

/* HDU2521 反素數 */#include <stdio.h>#define N 5000int apcount[N+1]; /* antiprime count */int getapcount(int n) {int count = 1, i;for(i=2; i<=n/2; i++)if(n % i == 0)count++; /* 因子個數計數 */if(n != 1)count++; /* 不是1則自身因子需要加上 */return count; }void setapcount(int n) {int i;apcount[0] = 0;for(i=1; i<=n; i++)apcount[i] = getapcount(i); }int main(void) {setapcount(N);int n, a, b, max, maxval, i;scanf("%d", &n);while(n--) {scanf("%d%d", &a, &b);max = maxval = 0;for(i=a; i<=b; i++)if(apcount[i] > maxval) {maxval = apcount[i];max = i;}printf("%d\n", max);}return 0; }

轉載于:https://www.cnblogs.com/tigerisland/p/7563640.html

總結

以上是生活随笔為你收集整理的HDU2521 反素数【因子数量+打表】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。