Question address: http://codeforces.com/contest/474/problem/F
From the meaning of the question, it can be seen that the minimum gcd that can be left in the end must be the interval. Then it is converted into the number equal to the minimum number of gcd in the interval. The minimum gcd of the interval must be less than or equal to the minimum value of the interval, so only the number of minimum values is required. Then use r-l 1-number.
The above information can be maintained using a line segment tree. Maintain the interval gcd, the interval minimum value and the number of interval minimum values respectively.
The code is as follows:
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64#define lson l, mid, rt<<1#define rson mid+1, r, rt<<1|1const int INF=0x3f3f3f3f;const int MAXN=100000;int minv[MAXN<<2], gcd[MAXN<<2], num[MAXN<<2], q_minv, q_gcd, q_num;int getgcd(int a, int b){ return a==0?b:getgcd(b%a,a);}void PushUp(int rt){ minv[rt]=min(minv[rt<<1],minv[rt<<1|1]); gcd[rt]=getgcd(gcd[rt<<1],gcd[rt<<1|1]); if(minv[rt<<1]==minv[rt<<1|1]) num[rt]=num[rt<<1]+num[rt<<1|1]; else if(minv[rt<<1]>minv[rt<<1|1]) num[rt]=num[rt<<1|1]; else num[rt]=num[rt<<1];}void build(int l, int r, int rt){ if(l==r) { scanf("%d",&minv[rt]); num[rt]=1; gcd[rt]=minv[rt]; return ; } int mid=l+r>>1; build(lson); build(rson); PushUp(rt);}void query(int ll, int rr, int l, int r, int rt){ if(ll<=l&&rr>=r) { q_gcd=getgcd(q_gcd,gcd[rt]); if(minv[rt]==q_minv) { q_num+=num[rt]; } else if(minv[rt]<q_minv) { q_num=num[rt]; q_minv=minv[rt]; } return ; } int mid=l+r>>1; if(ll<=mid) query(ll, rr, lson); if(rr>mid) query(ll,rr,rson);}int main(){ int n, m, i, l, r; scanf("%d",&n); build(1, n, 1); /*for(i=1;i<=9;i++) { printf("%d %d %d\n",minv[i], gcd[i], num[i]); }*/ scanf("%d",&m); while(m--) { scanf("%d%d",&l,&r); q_minv=INF; q_gcd=0; q_num=0; query(l,r,1,n,1); if(q_gcd==q_minv) { printf("%d\n",r-l+1-q_num); } else { printf("%d\n",r-l+1); } } return 0;}
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
