 ###### 编程介的小学生

2019-04-13 17:54 阅读 424

# 最大公约数的计算的一个代码算法程序，看下怎么来修改和实现的，用C语言

Problem Description
The greatest common divisor (gcd) of two or more integers (at least one of which is not zero) is the largest positive integer that divides the numbers without a remainder.

Now I will give you a simple problem about gcd again.

Given a sequence of N integers, A = {a1, a2, ..., aN }.

For every pair of < l, r >( 1 ≤ l ≤ r ≤ N ), defined a function F (l, r) = gcd(ai)( l ≤ i ≤ r ) that is the greatest common divisor of all the integers in the subsequence {al, al+1, ..., ar }

Obviously, There are N * (N + 1)/2 pair of < l, r >( 1 ≤ l ≤ r ≤ N ). We can get the rank of pair < l, r > through the following code.

1 pair get_RANK(int l,int r)
2 {
3 mapmp;
4 int k1 = 1, k2 = 1;
5 for(int i = 1;i <= N;i++)
6 for(int j = i;j <= N;j++)
7 {
8 if(i == l && j == r)continue;
9 if(F(i,j) < F(l,r))
10 {
11 if(mp.find(F(i,j)) != mp.end())continue;
12 k1++;
13 mp[F(i,j)] = 1;
14 }
15 else if(F(i,j) == F(l,r))
16 {
17 if(i < l || (i == l && j < r))k2++;
18 }
19 }
20 return make_pair(k1,k2);
21 }

(If you don’t know C++, what a sad story! Sorry!)

There are Q queries, you need to answer the following two queries:

● SELECT k1 k2: ask for the pair < l, r > which is rank < k1, k2 >.If there is no such pair output -1.

● RANK l r: ask for the rank < k1, k2 > of the pair < l, r >

Input
The first line of the input is T (1 ≤ T ≤ 10), which stands for the number of test cases you need to solve.

The first line of each case contains two integers N ,Q (1 ≤ N, Q ≤105),denoting the number of integers and queries, respectively.

The second line contains N integers, a1, a2, ..., aN (1 ≤ ai ≤ 105).

For the next Q lines, contain instructions “SELECT k1 k2” or “RANK l r” (1 ≤ k1, k2 ≤ N * (N + 1)/2,1 ≤ l ≤ r ≤ N ),

Output
For each test case, print a line “Case #t:”(without quotes, t means the index of the test case) at the beginning.

For each query, output the answer.

Sample Input
1
3 6
6 2 4
RANK 1 1
SELECT 3 1
RANK 2 3
SELECT 2 2
SELECT 1 3
SELECT 1 4

Sample Output
Case #1:
3 1
1 1
1 4
-1
2 2
2 3

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享