概述
Problem Description
This is a simple problem. The teacher gives Bob a list of problems about GCD (Greatest Common Divisor). After studying some of them, Bob thinks that GCD is so interesting. One day, he comes up with a new problem about GCD. Easy as it looks, Bob cannot figure it out himself. Now he turns to you for help, and here is the problem:
Given an array a of N positive integers a1,a2,⋯aN−1,aN; a subarray of a is defined as a continuous interval between a1 and aN. In other words, ai,ai+1,⋯,aj−1,aj is a subarray of a, for 1≤i≤j≤N. For a query in the form (L,R), tell the number of different GCDs contributed by all subarrays of the interval [L,R].
Input
There are several tests, process till the end of input.
For each test, the first line consists of two integers N and Q, denoting the length of the array and the number of queries, respectively. N positive integers are listed in the second line, followed by Q lines each containing two integers L,R for a query.
You can assume that
1≤N,Q≤100000
1≤ai≤1000000
Output
For each query, output the answer in one line.
Sample Input
5 3
1 3 4 6 9
3 5
2 5
1 5
Sample Output
6
6
6
树状数组的题…
思路就是先取所有的gcd一个一个找,大小区间都算
重复的就去重
还得多理解。。
补充:昨天有一些没想明白的地方但是太晚了就没在意…..
之所以不能全部处理完了再输出的原因就是因为
那个qujian 数组在遍历完了更高的区间以后存的下标就会变化
最后gs出来的不是想要的那个值
#include<stdio.h>
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<memory.h>
#include<vector>
using namespace std;
int q, w;
int di[100020];
int ci[100020];
int qujian[1000200];
int lowb(int x) { return x&(-x); }
int gcd(int a, int b)
{
if (b == 0) return a;
return gcd(b, a%b);
}
int gs(int x)//这是得到的值
{
int s = 0;
for (int a = x;a > 0;a -= lowb(a))s += ci[a];
return s;
}
struct p
{
int zuo, xiabiao;
};
vector<p>xia[100005];
int yuyu[100005];
void gengxin(int dizhi, int zhi){for (int a = dizhi;a <= q;a += lowb(a))ci[a] += zhi;}
int main()
{
while (cin >> q >> w)
{
memset(di, 0, sizeof(di));
memset(ci, 0, sizeof(ci));
memset(qujian, 0, sizeof(qujian));
for (int a = 1;a <= q;a++)scanf("%d", &di[a]),xia[a].clear();
int qq, ww;
for (int a = 1;a <= w;a++)
{
scanf("%d%d", &qq, &ww);
xia[ww].push_back({qq,a});
}
for (int a = 1;a <= q;a++)
{
for (int b = a, x = di[b];b > 0;b--, x = gcd(x, di[b]))
{
if (b > qujian[x])
{
if (qujian[x] != 0)gengxin(qujian[x], -1);//这是个判断重复的好办法
gengxin(b, 1);//每当碰见了就更新一次
qujian[x] = b;
}
if (x == 1)break;
}
for (int b = 0;b < xia[a].size();b++)yuyu[xia[a][b].xiabiao] = -gs(xia[a][b].zuo-1) + gs(a );
}
for (int a = 1;a <= w;a++)printf("%dn", yuyu[a]);
}
return 0;
}
最后
以上就是落后小笼包为你收集整理的HDU5869 树状数组的全部内容,希望文章能够帮你解决HDU5869 树状数组所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复