最大公约数的计算的一个代码算法程序,看下怎么来修改和实现的,用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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐