有一个集合 ，游戏开始时里面有一些数 ，xyx每次可以选择集合中的两个数 （这两个数可以是同一个数）相减，把它们的差的绝对值放入集合中（如果集合中已存在该数则不放入），经过任意次这样的操作后 ，xyx会给出一个数字k ，问它 是否能存在在集合中，如果能 ，那么游戏成功 ，反之失败。 （换句话说 ，xyx想知道这样不断操作下去 ，是否能凑出数字k ） xyx有一个数列a ，他每次会给出三个数l,r,x ，即把所有的 (l ≤ i ≤ r)放入集合中，并且想要知道当k = x时游戏是否成功有多组询问且询问之间相互独立 ，你可以认为每次询问后xyx就把游戏中的集合清空了
输入描述 第一行两个整数n 和m，分别表示数字集合的大小和询问次数。 第二行共n个整数 ，表示数列a ，第i个数是ai 。 接下来m 行 ，每行三个整数l,r,x ，含义见题目描述 输出描述 共m 行 ，每行一个字符串，表示对应询问的答案 ，如果游戏成功输出”win” ，反之输出”lose”。（不输出引号） 样例输入 7 5 3 6 4 2 7 1 8 1 2 3 3 7 0 3 4 2 3 4 5 2 3 3
样例输出
win win win lose lose 数据范围：非常大！！！
首先先想一下减法的性质： 1.对于一个数K，若是集合中的数都小于它，那肯定不能减出它。 2.如果集合中的数的gcd不能被k整除，显然也是不合法的 所以题目就变成了求一段区间的gcd，但是数据范围太大怎么办？ 我们可以用RMQ算法维护数据，分两段求出gcd，运用倍增的思想，查询时只要查询l+2^t,r-2^t+1覆盖的范围的gcd就可以了
#include<iostream> #include<cstdio> #define M 100005 using namespace std; int n,m,k,p,q,l,r; int a[M],g[M][20],maxx[M][20],bit[M]; int gcd(int a,int b){ if (b==0) return a; else return gcd(b,a%b); } void work(int l,int r,int &p,int &q){ int t=bit[r-l+1]; p=gcd(g[l][t],g[r-(1<<t)+1][t]); q=max(maxx[l][t],maxx[r-(1<<t)+1][t]); } int main(){ cin>>n>>m; for (int i=1;i<=n;i++) scanf("%d",&a[i]), g[i][0]=maxx[i][0]=a[i]; bit[0]=-1; for (int i=1;i<=n;i++) bit[i]=bit[i>>1]+1; for (int i=1;1<<i<=n;i++) for (int j=1;j+(1<<i)-1<=n;j++) { g[j][i]=gcd(g[j][i-1],g[j+(1<<i-1)][i-1]); maxx[j][i]=max(maxx[j][i-1],maxx[j+(1<<i-1)][i-1]); } for (int i=1;i<=m;i++){ scanf("%d%d%d",&l,&r,&k); work(l,r,p,q); if (!q) puts(!k?"win":"lose"); else puts(k<=q&&k%p==0?"win":"lose"); } return 0; }