?

?給定?n?個數(shù)字構成的一個多重集合：請求出，其中有多少元素不能被任意一個在集合中的其他元素整除？

?

無法通過的做法

int main() {int n;cin >> n;int* num = new int[n];for (int i = 0; i < n; i++) {cin >> num[i];}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j) {if (num[i] % num[j] == 0) {count++;break;}}}}cout << n - count;return 0; }

不難看出，這種做法的時間復雜度太高了?

正確的做法

利用?埃式篩法 來做，埃式篩法原本是用來在自然數(shù)中尋找素數(shù)的，檢查數(shù)字n是否為素數(shù)大體這么做：做一個標記數(shù)組，如果n沒有被標記過，說明它是質數(shù)，這時把的倍數(shù)全部標記。否則它是合數(shù)。

我們先把數(shù)字排序，再做一次埃式篩法就行了。

例如，對于例子中的數(shù)組中，出現(xiàn)了3，那么認為 6，9，12，15……999999 等數(shù)可以被標記為不符合要求的數(shù)，但3自己是符合要求的。

建立bool數(shù)組：
bool bs[1000010];
該數(shù)組表示對應下標的數(shù)是否在輸入的一系列數(shù)中存在除該數(shù)本身之外的因數(shù)，如果存在，說明能被整除。
然后每次輸入a時，都將從2*a到1000000的所有a的倍數(shù)的下標設為true，最后統(tǒng)計數(shù)組中對應下標的元素在集合中且為false的元素的個數(shù)即可。
但要注意本題的數(shù)字可能重復，一旦重復，則所有相同的數(shù)都不滿足不能被整除的條件了。所以建立另一個數(shù)組表示某元素是否存在：
bool ea[1000010];
在輸入a后，如果ea[a]為false，則說明a尚不存在，將其設為true并執(zhí)行將a的倍數(shù)設置的操作；如果ea[a]存在，則將bs[a]直接設為true。
?

解題代碼

#include<iostream> using namespace std; bool bs[1000010]; bool ea[1000010];int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {int a;cin >> a;if (!ea[a]) {ea[a] = true;}else {bs[a] = true;}for (int j = a + a; j <= 1000000; j += a) {bs[j] = true;}}int ans = 0;for (int i = 1; i <= 1000000; i++) {if (!ea[i]) continue;ans += !bs[i];}cout << ans;return 0; }

?

總結

以上是生活随笔為你收集整理的上海计算机协会竞赛平台——整除的全部內容，希望文章能夠幫你解決所遇到的問題。

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