You are given the value of m and (f(n,m)−n)⊕n, where ``⊕’’ denotes the bitwise XOR operation. Please write a program to find the sma
integer n that (f(n,m)−n)⊕n=k, or determine it is impossible.
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 are two integers k,m(1≤k≤1018,1≤m≤100).
Output
For each test case, print a single line containing an integer, denoting the smallest n. If there is no solution, output ``-1’’ instead.
Sample Input
12
23 5
36 100
Sample Output
15
2-1
题意
f (n, m) 代表比 n 大的第 m 个与 n 互质的数,现已知 (f(n,m)−n)⊕n 的值为 k,求 n 的值
分析
(f(n,m)−n)⊕n=k 可以写成 f(n,m)-n=n⊕k,因为 m 的值为 100,所以(f(n,m)−n) 的值比较小,则 n⊕k 的值比较小,说明 n 与 k 相接近,所以对 k-
51 之间的数进行遍历,找到适合的 n 即是答案。代码
1#include<bits/stdc++.h>
2using namespace std;
3int main(){
4 int t;
5 scanf("%d",&t);
6 long long k,i;
7 int m;
8 while(t--)
9 {
10 scanf("%lld%d",&k,&m);
11 if(k<512) i=1;
关闭
评论0