博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CodeChef Gcd Queries
阅读量:5876 次
发布时间:2019-06-19

本文共 2286 字,大约阅读时间需要 7 分钟。

Gcd Queries

 
Problem code:
GCDQ
 

All submissions for this problem are available.

Read problems statements in and .

You are given an array A of integers of size N. You will be given Q queries where each query is represented by two integers L, R. You have to find the (Greatest Common Divisor) of the array after excluding the part from range L to R inclusive (1 Based indexing). You are guaranteed that after excluding the part of the array

remaining array is non empty.

Input

  • First line of input contains an integer T denoting number of test cases.
  • For each test case, first line will contain two space separated integers N, Q.
  • Next line contains N space separated integers denoting array A.
  • For next Q lines, each line will contain a query denoted by two space separated integers L, R.

Output

For each query, print a single integer representing the answer of that query.

Constraints

Subtask #1: 40 points

  • 2 ≤ T, N ≤ 100, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 105
  • 1 ≤ L, R ≤ N and L ≤ R

Subtask #2: 60 points

  • 2 ≤ T, N ≤ 105, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 105
  • 1 ≤ L, R ≤ N and L ≤ R
  • Sum of N over all the test cases will be less than or equal to 106.

Example

Input:13 32 6 91 12 22 3Output:312

Explanation

For first query, the remaining part of array will be (6, 9), so answer is 3.

For second query, the remaining part of array will be (2, 9), so answer is 1.
For third query, the remaining part of array will be (2), so answer is 2.

Warning : Large IO(input output), please use faster method for IO.

 

求一个序列删去L~R后其余数的GCD ,,直接预处理一下前序GCD,后序GCD就OK~

 

#include 
using namespace std;const int N = 100010;int e[N],L[N],R[N],n,Q;void Run() { scanf("%d%d",&n,&Q); for( int i = 1 ; i <= n ; ++i ) scanf("%d",&e[i]); L[1] = e[1]; for( int i = 2 ; i <= n ; ++i ) L[i] = __gcd( e[i] , L[i-1] ) ; R[n] = e[n]; for( int i = n-1 ; i >= 1 ; --i ) R[i] = __gcd( e[i] , R[i+1] ) ; while(Q--){ int x , y ; scanf("%d%d",&x,&y); if( x > 1 ) { if( y < n )printf("%d\n",__gcd(L[x-1],R[y+1])); else printf("%d\n",L[x-1]); } else { if( y < n )printf("%d\n",R[y+1]); else puts("1"); } }}int main(){ int _ , cas = 1 ; scanf("%d",&_); while(_--)Run();}
View Code

 

转载于:https://www.cnblogs.com/hlmark/p/4296959.html

你可能感兴趣的文章
JavaScript高级程序设计--对象,数组(栈方法,队列方法,重排序方法,迭代方法)...
查看>>
【转】 学习ios(必看经典)牛人40天精通iOS开发的学习方法【2015.12.2
查看>>
nginx+php的使用
查看>>
在 ASP.NET MVC 中使用异步控制器
查看>>
SQL语句的执行过程
查看>>
Silverlight开发历程—动画(线性动画)
查看>>
详解Linux中Load average负载
查看>>
HTTP 协议 Cache-Control 头——性能啊~~~
查看>>
丢包补偿技术概述
查看>>
PHP遍历文件夹及子文件夹所有文件
查看>>
WinForm程序中两份mdf文件问题的解决
查看>>
【转】唯快不破:创业公司如何高效的进行产品研发管理
查看>>
程序计数器、反汇编工具
查看>>
Android N: jack server failed
查看>>
007-Shell test 命令,[],[[]]
查看>>
关于Linux系统使用遇到的问题-1:vi 打开只读(readonly)文件如何退出保存?
查看>>
pandas 按照某一列进行排序
查看>>
在WPF中如何使用RelativeSource绑定
查看>>
XSLT语法 在.net中使用XSLT转换xml文档示例
查看>>
如何将lotus 通讯簿导入到outlook 2003中
查看>>