# hdu - 6186 and hdu - 6025

Posted by WildCow on May 22, 2018

# CS Course

Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

### Description

Little A has come to college and majored in Computer and Science.
Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.
Here is the problem:
You are giving n non-negative integers , and some queries.
A query only contains a positive integer p, which means you
are asked to answer the result of bit-operations (and, or, xor) of all the integers except .

### Input

There are no more than 15 test cases.
Each test case begins with two positive integers n and p
in a line, indicate the number of positive integers and the number of queries.
Then n non-negative integers follows in a line, for each i in range[1,n].
After that there are q positive integers in q lines, for each i in range[1,q].

### Output

For each query p, output three non-negative integers indicates the result of bit-operations((and, or, xor)) of all non-negative integers except in a line.

3 3
1 1 1
1
2
3

1 1 0
1 1 0
1 1 0

# Coprime Sequence

Time Limit: 1000 ms
Memory Limit: 131072 kB

### Description

Do you know what is called “Coprime Sequence”? That is a sequence consists of n positive integers, and the GCD (Greatest Common Divisor) of them is equal to 1. “Coprime Sequence” is easy to find because of its restriction. But we can try to maximize the GCD of these integers by removing exactly one integer. Now given a sequence, please maximize the GCD of its elements.

### Input

The first line of the input contains an integer $T(1≤T≤10)$, denoting the number of test cases. In each test case, there is an integer $n(3≤n≤100000)$ in the first line, denoting the number of integers in the sequence. Then the following line consists of $n$ integers $a_1,a_2,…,a_n(1≤a_i≤10^9)$, denoting the elements in the sequence.

### Output

For each test case, print a single line containing a single integer, denoting the maximum GCD.

3
3
1 1 1
5
2 2 2 3 2
4
1 2 4 8

### Sample Output

1
2
2

1、给你 $n$ 个数 $a_1,a_2,…,a_n$ 和 $q$ 次询问，每次询问给你一个数 $x$，输出除了 $a_x$ 外的剩下数字的 $and, or, xor$ 的结果。

2、给你 $n$ 个数 $a_1,a_2,…,a_n$ ，你需要输出删除一个数后剩下数字的 GCD 的最大值。


/// Hdu - 6186
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int ma[N];
int a1[N], a2[N];
int b1[N], b2[N];
int c;

int main()
{
int n, m;

while(scanf("%d%d", &n, &m) == 2){
for(int i = 1; i <= n; i ++){
scanf("%d", &ma[i]);
}
a1[0] = (1 << 31) - 1;/// & 运算的初始值要每一位都为1
b1[0] = 0;
c = 0;
for(int i = 1; i <= n; i ++){
a1[i] = a1[i - 1] & ma[i];
b1[i] = b1[i - 1] | ma[i];
c ^= ma[i];
}
a2[n + 1] = (1 << 31) - 1;
b2[n + 1] = 0;
for(int i = n; i > 0; i --){
a2[i] = a2[i + 1] & ma[i];
b2[i] = b2[i + 1] | ma[i];
}
for(int i = 0; i < m; i ++){
int x;

scanf("%d", &x);
printf("%d %d %d\n", a1[x - 1] & a2[x + 1], b1[x - 1] | b2[x + 1], c ^ ma[x]);
}
}

return 0;
}



/// HDU - 6025
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int ma[N];
int mb[N];
int mc[N];

int main()
{
int ncase;
int n;
int li;
int ans;

scanf("%d", &ncase);
while(ncase --){
ans = -1;
scanf("%d", &n);
for(int i = 0; i < n; i ++){
scanf("%d", &ma[i]);
if(i == 0){
mb[i] = ma[i];
}
mb[i] = __gcd(ma[i], mb[i - 1]);
}
mc[n - 1] = ma[n - 1];
for(int i = n - 2; i >= 0; i --){
mc[i] = __gcd(ma[i], mc[i + 1]);
}
li = n - 1;
for(int i = 1; i < n; i ++){
ans = max(ans, __gcd(mb[i - 1], mc[i + 1]));
}
ans = max(ans, mb[n - 2]);
ans = max(ans, mc[1]);
printf("%d\n", ans);
}

return 0;
}