Codeforces Contest 1110 problem C Meaningless Operations——找区间内两个数的与和异或的最大gcd

本文主要是介绍Codeforces Contest 1110 problem C Meaningless Operations——找区间内两个数的与和异或的最大gcd，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Can the greatest common divisor and bitwise operations have anything in common? It is time to answer this question.

Suppose you are given a positive integer a. You want to choose some integer b from 1 to a−1 inclusive in such a way that the greatest common divisor (GCD) of integers a⊕b and a&b is as large as possible. In other words, you’d like to compute the following function:

f(a)=max0<b<agcd(a⊕b,a&b).
Here ⊕ denotes the bitwise XOR operation, and & denotes the bitwise AND operation.

The greatest common divisor of two integers x and y is the largest integer g such that both x and y are divided by g without remainder.

You are given q integers a1,a2,…,aq. For each of these integers compute the largest possible value of the greatest common divisor (when b is chosen optimally).

Input
The first line contains an integer q (1≤q≤103) — the number of integers you need to compute the answer for.

After that q integers are given, one per line: a1,a2,…,aq (2≤ai≤225−1) — the integers you need to compute the answer for.

Output
For each integer, print the answer in the same order as the integers are given in input.

Example
inputCopy
3
2
3
5
outputCopy
3
1
7
Note
For the first integer the optimal choice is b=1, then a⊕b=3, a&b=0, and the greatest common divisor of 3 and 0 is 3.

For the second integer one optimal choice is b=2, then a⊕b=1, a&b=2, and the greatest common divisor of 1 and 2 is 1.

For the third integer the optimal choice is b=2, then a⊕b=7, a&b=0, and the greatest common divisor of 7 and 0 is 7.

题意：

给你一个数a，你要在1到a-1之间找一个数，使得gcd(a&b,a⊕b)最大。

题解：

数学的1500难度对我来说就相当于1700了，想了一会才想到怎么做。。首先第一种不是$2^k-1$的数，很明显可以从note里面看出来就是$2^k-1$，因为我们可以找到一个数b，使得b&a=0,b|a=$2^n-1$，那么就是这个数了，还有一种是找到他的最大因子。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int p[N],np[N],cnt;
void init()
{for(ll i=2;i<N;i++){if(!np[i]){p[++cnt]=i;for(ll j=i*i;j<N;j+=i)np[j]=1;}}
}
int main()
{init();int q;scanf("%d",&q);while(q--){int a;scanf("%d",&a);int ret=1,cnt=0;while(ret<=a)ret*=2,cnt++;if(ret-1==a){int ans=a;for(int i=1;i<=cnt&&p[i]<=sqrt(a);i++){if(a%p[i]==0){ans=p[i];break;}}printf("%d\n",a/ans);}elseprintf("%d\n",ret-1);}return 0;
}

这篇关于Codeforces Contest 1110 problem C Meaningless Operations——找区间内两个数的与和异或的最大gcd的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---