Educational Codeforces Round 14 - F (codeforces 691F)

题目链接：http://codeforces.com/problemset/problem/691/F

题目大意：给定n个数，再给m个询问，每个询问给一个p，求n个数中有多少对数的乘积≥p

数据范围：2≤n≤10^6, 1≤ai≤3*10^6，1≤m≤10^6, 1≤p≤3*10^6

解题思路：比赛的时候比较naive的思路是把n中的数字排序去了重之后，对于每个p，最多枚举√p步，就能得到答案。而这个naive的思路是O（p√p）的，结果T了。

后来百思不得其解，去看了官方的解答。感觉是一种很有必要总结的思路。思路的模型是埃氏筛素数。

筛素数中枚举到一个素数pr，我们就把MAX范围内的pr的倍数依次搭上标记。这样做看似暴力，实际上复杂度近乎O（n）（其实是O(MAX/p1+MAX/p2..MAX/pk）)

回到这道题目，完全可以借鉴上述思路，从1-MAX枚举a，再从1-MAX/a枚举另一半b，记n个数中乘积等于i的对数ans[i]，那么就有ans[a*b] += cnt[a]*cnt[b];其中cnt[i]表示n个数中i这个数出现了多少次。仔细分析复杂度的话是O（MAX/1+MAX/2+MAX/3+...+MAX/MAX），事实上，这个东西是接近O（MAXlogMAX）的，这种思想在处理一些数论问题中同样很有借鉴意义。我认为这种思路复杂度的支撑点在于他有一个上限MAX，并且内部的操作是相乘。

最后得到了ans[i]之后取个前缀和就得到了n个数中乘积<p的对数,用总对数一减就得到了答案。

#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

 

转载于:https://www.cnblogs.com/ChopsticksAN/p/5727819.html

总结

以上是生活随笔为你收集整理的Educational Codeforces Round 14 - F (codeforces 691F)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。