codeforces 475D
2024-08-22 08:29:24
题意:给定n(n<=100000)个1e9以内的数的数组a,然后最多有3*1e5的询问,对于每个询问,给定一个x,问有多少个(l<=r&&gcd(a[l],a[l+1]...a[r]) == x)
思路:昨天的比赛题。。可惜我被c题wa到放弃了这场比赛。。也就没看了。。不妨设G(l,r) = gcd(a[l], a[l+1]...a[r]);
其实题目最关键的的性质是对于G(l,r),G(l,r+1)后者肯定比前者更小。。
所以就可以暴力了。。从后往前扫描i,处理(i, n)这一段区间,处理处理完之后,就会出现G(i,i),G(i,i+1)..G(i, n),并且是递减的
所以相邻之间如果相同,我们就可以合并,具体操作可以用链表。。
这样最坏情况下每个数求log(1e9)次gcd,所以还是可以快速过的。。
code:
#include <bits/stdc++.h>
using namespace std;
int a[], nxt[], n;
map<int, long long> mp; void solve(){
for (int i = ; i <= n; ++i)
scanf("%d", &a[i]), nxt[i] = i + ;
mp.clear();
for (int i = n; i >= ; --i){
int g = a[i], pre_g = g, pre = i;
for (int j = i; j <= n + ; j = nxt[j]){
if (j == n + ){
mp[pre_g] += (j - pre);
nxt[pre] = j;
break;
}
g = __gcd(a[j], g);
if (g != pre_g)
mp[pre_g] += (j - pre) , nxt[pre] = j , pre = j, pre_g = g;
}
}
int q, x;
scanf("%d", &q);
while (q--){
scanf("%d", &x);
printf("%I64d\n",mp[x]);
}
} int main(){
while (scanf("%d", &n) != EOF){
solve();
}
}
最新文章
- js遍历json
- 回忆:#define的用法
- 使用Mulesoft建立webservice, simple方式,POJO
- React Native填坑之旅--重新认识RN
- IQ推理:P先生和Q先生
- mysql修改definer方法
- yii2框架安装
- php之上传类
- 静态Web开发 HTML
- HDU-1020(水题)
- python 格式化日期
- (C++编程规范第17条)避免使用”魔数“
- 使用ACE获取主机的IP地址
- sqlserver不能直接create table as select
- 转 当当网资深DBA:DB运维四大现代化的实现
- Exchange无法发送邮件 未找到匹配的连接器来路由外部收件人解决办法
- GitHub 添加 SSH keys
- java中使用poi导出excel表格数据并且可以手动修改导出路径
- [Swift]动态变化顶部状态栏(statusBar)的颜色
- 老男孩Python全栈学习 S9 日常作业 008