[原创]HDU 5726 GCD [ST表+暴力二分]【数据结构|杂类】
[原创]HDU 5726 GCD [ST表+暴力二分]【数据结构|杂类】
2017-01-24 17:26:37 Tabris_ 阅读数:305
博客爬取于2020-06-14 22:41:57
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54709231
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5726
-----------------------------------------------------------------------.
GCD
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3164 Accepted Submission(s): 1146
Problem Description
Give you a sequence of N(N≤100,000) integers : a1,…,an(0 < ai≤1000,000,000). There are Q(Q≤100,000) queries. For each query l,r you have to calculate gcd(al,al+1,…,ar) and count the number of pairs(l′,r′)(1≤l< r≤N)such that gcd(al′,al′+1,…,ar′) equal gcd(al,al+1,…,ar).
Input
The first line of input contains a number T, which stands for the number of test cases you need to solve.
The first line of each case contains a number N, denoting the number of integers.
The second line contains N integers, a1,…,an( 0 < ai ≤ 1000,000,000).
The third line contains a number Q, denoting the number of queries.
For the next Q lines, i-th line contains two number , stand for the li,ri, stand for the i-th queries.
Output
For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).
For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,…,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,…,ar′) equal gcd(al,al+1,…,ar).
Sample Input
1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4
Sample Output
Case #1:
1 8
2 4
2 4
6 1
Author
HIT
-----------------------------------------------------------------------.
题目大意:
有一个长度为N的序列,Q次查询,每次查询需求解出及与区间gcd值相同的区间有多少个.
解题思路
首先对与区间gcd 我们可以用线段树或者ST表预处理下,因为没有元素更改,相比之下后者更好(复杂度上,代码量上)
然后就是如何就解与区间gcd值相同的区间有多少个.
这个我们只能枚举一端,然后向右找,然后用个map来存储结果,这样的话复杂度是,显然不可取.
但是对于一个区间上的gcd来说一定是不增的.这样就有了单调性,我们就可以二分做了,但这样需要三层循环解决.,而且在枚举不同端点的时候还会有重复统计的情况.
然后考虑,一个gcd的递减的过程最多也就这能递减因子数个,那么我们每一次记录的就是一种gcd值的区间,然后接下来串过来就好了,
最后的复杂度就是
附本题代码
-----------------------------------------------------------------------.
1 | # include <bits/stdc++.h> |