跟ACM 160類似。
先做質因數分解,再用質因數分解的答案算出所有因數。
例如6是 2^1 * 3^1,所以6的所有因數為(1 + 1) * (1 + 1) = 4。
題目已經告訴我們1000000000中最多是192個因數。
所以會用到的質數一定小於192。
但這時候會有個問題,如果是給的值,是第193以後的質數怎麼辦?
因為質數只能被自己跟1整除,所以也不會被其他質數整除。
反正質數的因數就只有2個,所以質數也可以處理了。
老實說我一開始沒想到第193個質數之後的情況,
但寫出來的程式碼也誤打誤撞AC =.=,
可能測資過了,但程式碼還是要修。
後來終於找到一個想法跟我差不多的人寫得程式碼,
好厲害!他補完了我沒想到的部份:
連結
完整假設是這樣:
因為合數必定可以拆成兩個質數相乘。
如果存在一組質數,使得p1 * p2 > 1000000000,
而p1, p2之前的質數相乘都能 < 1000000000的話,
那麼在1000000000這些數中,
最多最多會用到的質數,就是比p1或p2小的質數,
這要怎麼證明呢?
因為合數n必定可以拆成a * b,
a跟b必有一數大於等於根號n,另一數小於等於根號n,
所以我們只要找等於根號n的那個質數即可。
大於等於根號n的質數不用找,因為a跟b都要考慮,
若一個是大於等於根號n,那另一個必定小於等於根號n,
如此,只要找到小於等於根號n的所有情況,
也就滿足所有情況了。
第3401個質數為31607,31607的平方為999002449,
第3402個質數為31627,31627的平方為1000267129。
所以最多最多會用到的質數就是第3401個質數為31607。
總結,
只要考慮能被前3402個質數整除即可,
再用質因數分解的方式去找所有質數即可。
若合數n最後不是等於1,表示存在一個質數p,
使得前3402個質數都無法整除此質數p。
這種情況也不用擔心,因為能整除質數數只有兩種,
1跟他自己。
所以再把答案 * 2即可。
/* ACM 294 Divisors * mythnc * 2011/11/17 12:13:07 * run time: 0.032 */ #include <stdio.h> #define MAXP 3402 #define TRUE 1 #define FALSE 0 typedef struct divisor { int number, count; } Divisor; typedef struct big { int number, sum; } Big; void findp(Divisor *); Big maxn(Divisor *, int, int); int dnumber(Divisor *, int); int main(void) { int head, tail; Big max; Divisor prime[MAXP]; findp(prime); scanf("%*d"); while (scanf("%d %d", &head, &tail) == 2) { max = maxn(prime, head, tail); printf("Between %d and %d, %d has a maximum of %d divisors.\n" , head, tail, max.number, max.sum); } return 0; } /* findp: find n primes */ void findp(Divisor *p) { int count, i, j, flag; p[0].number = 2; count = 1; for (i = 3; count < MAXP; i += 2) { for (flag = TRUE, j = 3; j * j <= i; j++) if (i % j == 0) { flag = FALSE; break; } if (flag) p[count++].number = i; } } /* maxn: return the number which has the max divisors */ Big maxn(Divisor *p, int head, int tail) { int i, number; Big max; max.number = head; max.sum = dnumber(p, head); for (i = head + 1; i < tail + 1; i++) { number = dnumber(p, i); if (max.sum < number) { max.sum = number; max.number = i; } } return max; } /* dnumber: return number of divisors of n */ int dnumber(Divisor *p, int n) { int i, j, d; if (n == 1) return 1; for (i = 0; i < MAXP && n != 1; i++) { p[i].count = 0; while (n % p[i].number == 0) { n /= p[i].number; p[i].count++; } } for (d = 1, j = 0; j < i; j++) if (p[j].count != 0) d *= p[j].count + 1; if (n != 1) return d * 2; return d; }
沒有留言:
張貼留言