当前位置:网站首页>Codeforces 474 F. Ant colony
Codeforces 474 F. Ant colony
2022-07-07 20:03:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
线段树求某一段的GCD…..
F. Ant colony
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.
In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l and r(1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si).
After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.
In order to choose the best sequence, Mole gives you t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.
Input
The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony.
The second line contains n integers s1, s2, …, sn (1 ≤ si ≤ 109), the strengths of the ants.
The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases.
Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.
Output
Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [li, ri].
Sample test(s)
input
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
output
4
4
1
1
Note
In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.
In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.
In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.
In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int maxn=100100;
typedef pair<int,int> pII;
pII b[maxn];
int n,s[maxn];
int g[maxn<<2];
int gcd(int x,int y)
{
if(x==0) return y;
return gcd(y%x,x);
}
void build(int l,int r,int rt)
{
if(l==r)
{
g[rt]=s[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,rt<<1); build(mid+1,r,rt<<1|1);
g[rt]=gcd(g[rt<<1],g[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt)
{
if(r<L||l>R) return 0;
if(L<=l&&r<=R)
{
return g[rt];
}
int mid=(l+r)/2;
int u=query(L,R,l,mid,rt<<1);
int v=query(L,R,mid+1,r,rt<<1|1);
return gcd(u,v);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",s+i);
b[i]=(make_pair(s[i],i));
}
sort(b+1,b+1+n);
build(1,n,1);
int m;
scanf("%d",&m);
while(m--)
{
int Left,Right;
scanf("%d%d",&Left,&Right);
int G=query(Left,Right,1,n,1);
int from=lower_bound(b+1,b+n+1,make_pair(G,Left))-(b+1);
int to=lower_bound(b+1,b+1+n,make_pair(G,Right+1))-(b+1);
printf("%d\n",(Right-Left+1)-(to-from));
}
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116374.html原文链接:https://javaforall.cn
边栏推荐
- How does codesonar help UAVs find software defects?
- 九度 1201 -二叉排序数遍历- 二叉排序树「建议收藏」
- 上海交大最新《标签高效深度分割》研究进展综述,全面阐述无监督、粗监督、不完全监督和噪声监督的深度分割方法
- 恶魔奶爸 B3 少量泛读,完成两万词汇量+
- 论文解读(ValidUtil)《Rethinking the Setting of Semi-supervised Learning on Graphs》
- Flask1.1.4 Werkzeug1.0.1 源码分析:路由
- 目标:不排斥 yaml 语法。争取快速上手
- 数值法求解最优控制问题(〇)——定义
- 死锁的产生条件和预防处理[通俗易懂]
- 程序猿赚的那点钱算个P啊!
猜你喜欢
神兵利器——敏感文件发现工具
H3C S7000/S7500E/10500系列堆叠后BFD检测配置方法
95年专注安全这一件事 沃尔沃未来聚焦智能驾驶与电气化领域安全
最新版本的CodeSonar改进了功能安全性,支持MISRA,C ++解析和可视化
C language helps you understand pointers from multiple perspectives (1. Character pointers 2. Array pointers and pointer arrays, array parameter passing and pointer parameter passing 3. Function point
万字总结数据存储,三大知识点
Codesonar enhances software reliability through innovative static analysis
让这个CRMEB单商户微信商城系统火起来,太好用了!
I Basic concepts
机械臂速成小指南(十一):坐标系的标准命名
随机推荐
Network principle (1) - overview of basic principles
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
201215-03-19—cocos2dx内存管理–具体解释「建议收藏」
Numerical method for solving optimal control problem (0) -- Definition
刚开户的能买什么股票呢?炒股账户安全吗
Dachang classic pointer written test questions
Tensorflow2. How to run under x 1 Code of X
凌云出海记 | 赛盒&华为云:共助跨境电商行业可持续发展
恢复持久卷上的备份数据
静态测试工具
openGl超级宝典学习笔记 (1)第一个三角形「建议收藏」
Micro service remote debug, nocalhost + rainbow micro service development second bullet
The latest version of codesonar has improved functional security and supports Misra, c++ parsing and visualization
写一下跳表
嵌入式系统真正安全了吗?[ OneSpin如何为开发团队全面解决IC完整性问题 ]
测量楼的高度
Write a jump table
Helix QAC 2020.2 new static test tool maximizes the coverage of standard compliance
I Basic concepts
【奖励公示】第22期 2022年6月奖励名单公示:社区明星评选 | 新人奖 | 博客同步 | 推荐奖