欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  web前端

Codeforces Round #271 (Div. 2) F题 Ant colony（线段树）_html/css_WEB-ITnose

程序员文章站 2022-06-05 14:07:02
...
题目地址：http://codeforces.com/contest/474/problem/F

由题意可知，最后可以留下来的一定是区间最小gcd。那就转化成了该区间内与区间最小gcd数相等的个数。区间最小gcd一定小于等于区间最小值，所以只要求最小值的个数。然后用r-l+1-个数即可。

对于以上信息，可以用线段树来维护。分别维护区间gcd，区间最小值以及区间最小值的个数。

代码如下：

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL __int64#define lson l, mid, rtminv[rt>1;    build(lson);    build(rson);    PushUp(rt);}void query(int ll, int rr, int l, int r, int rt){    if(ll=r)    {        q_gcd=getgcd(q_gcd,gcd[rt]);        if(minv[rt]==q_minv)        {            q_num+=num[rt];        }        else if(minv[rt]>1;    if(llmid) query(ll,rr,rson);}int main(){    int n, m, i, l, r;    scanf("%d",&n);    build(1, n, 1);    /*for(i=1;i
相关标签： round colony codeforces div. 线段

上一篇： get_include_path ()的有关问题

下一篇： jQuery的animate方法在IE7下没作用_html/css_WEB-ITnose

推荐阅读