【HDU5726 2016 Multi-University Training Contest 1D】【gcd的下降性质 STL-map】GCD 多少段区间gcd等于给定区间gcd

本文主要是介绍【HDU5726 2016 Multi-University Training Contest 1D】【gcd的下降性质 STL-map】GCD 多少段区间gcd等于给定区间gcd，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

GCD

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2189 Accepted Submission(s): 731

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

Sample Output

  Case #1:
1 8
2 4
2 4
6 1

Author

HIT

Source

2016 Multi-University Training Contest 1

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, v[N];
vector< pair<int,int> >lft[N];
int gcd(int x, int y)
{return y == 0 ? x : gcd(y, x%y);
}
map<int, LL>mop;
void STinit()
{lft[n + 1].clear(); for (int i = n; i >= 1; i--){lft[i].clear();int p = i; int g = v[i];for (auto& it : lft[i + 1]){int newg = gcd(g, it.second);if (newg != g)lft[i].push_back(MP(p, g));p = it.first;g = newg;}lft[i].push_back(MP(p, g));p = i - 1;for (auto& it : lft[i]){mop[it.second] += it.first - p;p = it.first;}}
}
int getgcd(int l, int r)
{for (auto& it : lft[l]){if (r <= it.first)return it.second;}
}
int main()
{scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){mop.clear();scanf("%d", &n); for (int i = 1; i <= n; ++i)scanf("%d", &v[i]);STinit();int q; scanf("%d", &q);printf("Case #%d:\n", casei);while (q--){int l, r; scanf("%d%d", &l, &r);int g = getgcd(l, r);printf("%d %lld\n", g, mop[g]);}}return 0;
}
/*
【trick&&吐槽】
比赛的时候把最后一个区间段忘记加进去了，导致吃了一发WA，悲剧！【题意】
有n（1e5）个数，
每次给你一个区间段，
问你有多少个区间段内的gcd与该区间段的gcd是相同的，输出这样的区间个数。【类型】
gcd的下降性质【分析】
我们以一个点为区间的左界，然后逐渐扩展右界，gcd一旦变化了，至少也会变为原来的一半。
所以gcd的变化区间段数最多为logn段。
于是我们可以以区间的右侧开始，向右方向扩展gcd，然后存到map中。
这个预处理的复杂度是O(nlogn)
接下来对于单组数据的查询和询问，复杂度也是O(nlogn)，这道题就做完了。【时间复杂度&&优化】
O(nlogn)*/

这篇关于【HDU5726 2016 Multi-University Training Contest 1D】【gcd的下降性质 STL-map】GCD 多少段区间gcd等于给定区间gcd的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！