Educational Codeforces Round 14 - F (codeforces 691F)
2024-09-03 23:20:08
题目链接: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 + ], p[MaxN + ];
LL cnt[MaxN + ], sum[MaxN + ]; int main()
{
while (~scanf("%d", &n)) {
memset(cnt, , sizeof(cnt));
memset(sum, , sizeof(sum));
for (int i = ; i <= n; i++)
scanf("%d", &a[i]), cnt[a[i]]++;
scanf("%d", &m); MaX = -( << );
for (int i = ; i <= m; i++)
scanf("%d", &p[i]), MaX = max(MaX, p[i]);
for (int i = ; i <= MaX; i++)
for (int j = ; 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 = ; i <= MaX; i++) sum[i] += sum[i - ];
for (int i = ; i <= m; i++)
printf("%I64d\n", (LL)n * (n - ) - sum[p[i] - ]);
}
}
最新文章
- Bootstrap 3的box-sizing样式导致UEditor控件的图片无法正常缩放
- Quartz 框架的应用
- 自定义动画方法animate
- 关于tableView中tableHeaderView/tableFooterView/sectionHeader/sectionFooter/contentInset的理解
- poj1860 bellman—ford队列优化 Currency Exchange
- 编译android源码官方教程(3)下载代码
- 前端之JavaScript第二天学习(4)-JavaScript-注释
- Hibernate逍遥游记-第13章 映射实体关联关系-001用外键映射一对一(<;many-to-one unique=";true";>;、<;one-to-one>;)
- c#集合类的线程安全
- mysql学习(用户权限管理)
- CSDN博客排名第一名,何许人也
- BZOJ_2502_清理雪道_有源汇上下界最小流
- 【easy】268. Missing Number
- 2019-1-18 Spark 机器学习
- xss挑战之旅wp
- P2440 木材加工(二分+贪心)
- Jacob 调用金税系统
- 小文笔记 - phantomjs
- HPU1460: 杨八方的表面兄弟
- iOS问题#解决方案#之关于“application/x-www-form-urlencoded;charset=utf-8” not supported