当前位置:网站首页>#775 Div.1 B. Integral Array 数学
#775 Div.1 B. Integral Array 数学
2022-07-05 04:43:00 【Strezia】
B
1800
题意
给出一个含 n n n 个数的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an,并给出 c c c ,表示序列中所有数大小都不超过 c c c。我们称序列是整的当且仅当对于序列中任意两个(或同一个)数 x , y ( x ≤ y ) x,y(x\leq y) x,y(x≤y) , 满足 ⌊ y x ⌋ \lfloor \frac yx\rfloor ⌊xy⌋ 也在序列中。问这个序列是否是整的。 ( n ≤ 1 e 6 ) (n\leq1e6) (n≤1e6)
思路
这种题第一反应就是用类似素数筛的方法去优化,把对 r = ⌊ y x ⌋ r=\lfloor \frac yx\rfloor r=⌊xy⌋ 的判断改成对 y y y 的判断,不能拆成 x 和 r x和r x和r ”,所以可以枚举所有的 x x x,并枚举所有 r ∉ a r\notin a r∈/a , 如果在 x × r x\times r x×r 对应的范围内存在 y y y,则 r = ⌊ y x ⌋ ∉ a r=\lfloor \frac yx\rfloor\notin a r=⌊xy⌋∈/a ,不是整的。对应的范围即为 [ r × x , r × x + x − 1 ] [r\times x,r\times x + x - 1] [r×x,r×x+x−1],是否存在 y y y 只要预处理前缀和就可以了。
由调和级数,时间复杂度 O ( c log c ) O(c\log c) O(clogc) 。
代码
int cnt[maxn], sum[maxn];
void solve() {
int n, c;
cin >> n >> c;
for(int i = 1; i <= c; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
cnt[x]++;
}
sum[0] = 0;
for(int i = 1; i <= c; i++) {
sum[i] = sum[i-1] + cnt[i];
}
for(int x = 1; x <= c; x++) {
if(!cnt[y]) {
continue;
}
for(int i = 1; i * x <= c; i++) {
if(cnt[i]) continue;
int l = i * x - 1;
int r = min((i+1)*x-1, c);
if(sum[r] - sum[l]) {
cout << "No\n";
return;
}
}
}
cout << "Yes\n";
}
边栏推荐
- Stage experience
- 【acwing】836. Merge sets
- 托管式服务网络:云原生时代的应用体系架构进化
- CUDA Programming atomic operation atomicadd reports error err:msb3721, return code 1
- [groovy] closure (Introduction to closure class closure | this, owner, delegate member assignment and source code analysis)
- 2022 thinking of mathematical modeling a problem of American college students / analysis of 2022 American competition a problem
- Decryption function calculates "task state and lifecycle management" of asynchronous task capability
- Scope of package class package
- Introduction to RT thread kernel (4) -- clock management
- JVM 原理和流程简介
猜你喜欢
2022-2028 global and Chinese video coding and transcoding Market Research Report
自动语音识别(ASR)研究综述
Is $20billion a little less? Cisco is interested in Splunk?
概率论与数理统计考试重点复习路线
Key review route of probability theory and mathematical statistics examination
直播预告 | 容器服务 ACK 弹性预测最佳实践
[uniapp] system hot update implementation ideas
Sequence diagram of single sign on Certification Center
3 minutes learn to create Google account and email detailed tutorial!
Cookie learning diary 1
随机推荐
[Business Research Report] Research Report on male consumption trends in other economic times -- with download link
History of web page requests
Neural networks and deep learning Chapter 3: linear model reading questions
2022-2028 global and Chinese FPGA prototype system Market Research Report
MySQL in-depth learning - index creation and deletion, index design principles, index failure scenarios, query optimization, index push down ICP
Debug insights
CSDN body auto generate directory
如何进行「小步重构」?
Matplotlib draws three-dimensional scatter and surface graphs
flutter 对象和列表
Flutter 小技巧之 ListView 和 PageView 的各种花式嵌套
Flutter tips: various fancy nesting of listview and pageview
电源管理总线 (PMBus)
JMeter -- distributed pressure measurement
WeNet:面向工业落地的E2E语音识别工具
[PCL self study: feature9] global aligned spatial distribution (GASD) descriptor (continuously updated)
可观测|时序数据降采样在Prometheus实践复盘
Raki's notes on reading paper: code and named entity recognition in stackoverflow
English topic assignment (27)
函数(基本:参数,返回值)