本文主要是介绍HDU 5726 - GCD，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
题意：给出几个数字和一个操作次数，每个次操作给出一个区间，求出在这个区间内所有数的GCD，和这个GCD相同的数的区间个数。
因为数据规模太大，所以想到了用二分，ans[i][j] 表示从 i 这个数往后面 2^j 个数的GCD，公式是：ans[j][i] = GCD(ans[j][i-1], ans[j + (1<<i-1)][i-1])
二分注意是 2^j 之间进行二分，所以可以用 log2() 函数
最后统计好区间并进行计算
想了半下午，头都要炸了。。区域赛的GCD真难
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;int ans[100000+5][20];
int num[100000+5];
int n;
map<int, long long> M;int GCD(int a, int b)
{return b ? GCD(b, a%b) : a;
}void RMQ()
{for (int i = 1; i <= n; ++i)ans[i][0] = num[i];for (int i = 1; i < 18; ++i){for (int j = 1; j <= n; ++j){if (j + (1<<i) - 1 <= n)ans[j][i] = GCD(ans[j][i-1], ans[j + (1<<i-1)][i-1]);}}//printf("RMQ finish\n");
}int solve(int left, int right)
{int mid_bit = (int)log2((double)(right - left + 1));return GCD(ans[left][mid_bit], ans[right - (1<<mid_bit) + 1][mid_bit]);
}void setM()
{//printf("begin setM\n");M.clear();for (int i = 1; i <= n; ++i){int key = ans[i][0];int pos = i;while (pos <= n){int left = pos;int right = n;while (left < right){int mid = (left + right + 1) >> 1;if (solve(i, mid) == key)left = mid;elseright = mid - 1;}M[key] += left - pos + 1;pos = left + 1;key = solve(i, pos);}}//printf("setM finish\n");
}int main()
{int T, m;scanf("%d", &T);for (int icase = 1; icase <= T; ++icase){printf("Case #%d:\n", icase);scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d", &num[i]);RMQ();setM();scanf("%d", &m);for (int i = 1; i <= m; ++i){int left, right;scanf("%d%d", &left, &right);int ret = solve(left, right);printf("%d %I64d\n", ret, M[ret]);}}return 0;
}
这篇关于HDU 5726 - GCD的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
