題目鏈接：http://codeforces.com/problemset/problem/691/F

題目大意：給定n個數(shù)，再給m個詢問，每個詢問給一個p，求n個數(shù)中有多少對數(shù)的乘積≥p

數(shù)據(jù)范圍：2≤n≤10^6, 1≤ai≤3*10^6，1≤m≤10^6, 1≤p≤3*10^6

解題思路：比賽的時候比較naive的思路是把n中的數(shù)字排序去了重之后，對于每個p，最多枚舉√p步，就能得到答案。而這個naive的思路是O（p√p）的，結(jié)果T了。

后來百思不得其解，去看了官方的解答。感覺是一種很有必要總結(jié)的思路。思路的模型是埃氏篩素數(shù)。

篩素數(shù)中枚舉到一個素數(shù)pr，我們就把MAX范圍內(nèi)的pr的倍數(shù)依次搭上標(biāo)記。這樣做看似暴力，實際上復(fù)雜度近乎O（n）（其實是O(MAX/p1+MAX/p2..MAX/pk）)

回到這道題目，完全可以借鑒上述思路，從1-MAX枚舉a，再從1-MAX/a枚舉另一半b，記n個數(shù)中乘積等于i的對數(shù)ans[i]，那么就有ans[a*b] += cnt[a]*cnt[b];其中cnt[i]表示n個數(shù)中i這個數(shù)出現(xiàn)了多少次。仔細(xì)分析復(fù)雜度的話是O（MAX/1+MAX/2+MAX/3+...+MAX/MAX），事實上，這個東西是接近O（MAXlogMAX）的，這種思想在處理一些數(shù)論問題中同樣很有借鑒意義。我認(rèn)為這種思路復(fù)雜度的支撐點在于他有一個上限MAX，并且內(nèi)部的操作是相乘。

最后得到了ans[i]之后取個前綴和就得到了n個數(shù)中乘積<p的對數(shù),用總對數(shù)一減就得到了答案。

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef long long LL;const int MaxN = 3e6; int n, m, MaX; int a[MaxN + 5], p[MaxN + 5]; LL cnt[MaxN + 5], sum[MaxN + 5];int main() {while (~scanf("%d", &n)) {memset(cnt, 0, sizeof(cnt));memset(sum, 0, sizeof(sum));for (int i = 1; i <= n; i++) scanf("%d", &a[i]), cnt[a[i]]++;scanf("%d", &m); MaX = -(1 << 30);for (int i = 1; i <= m; i++) scanf("%d", &p[i]), MaX = max(MaX, p[i]);for (int i = 1; i <= MaX; i++)for (int j = 1; i * j <= MaX; j++)if (i != j) sum[i * j] += cnt[i] * cnt[j];else sum[i * j] += cnt[i] * cnt[i] - cnt[i];for (int i = 1; i <= MaX; i++) sum[i] += sum[i - 1];for (int i = 1; i <= m; i++) printf("%I64d\n", (LL)n * (n - 1) - sum[p[i] - 1]);} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/ChopsticksAN/p/5727819.html

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 14 - F (codeforces 691F)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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