Problem Description
For a positive integer
n, let's denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11.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 smallest positive 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
2 3 5 6 100
Sample Output
5 -1
Source
2019 Multi-University Training Contest 6
题解：
///
/// _ooOoo_
/// o8888888o
/// 88" . "88
/// (| -_- |)
/// O\ = /O
/// ____/`---'\____
/// .' \\| |// `.
/// / \\||| : |||// \
/// / _||||| -:- |||||- \
/// | | \\\ - /// | |
/// | \_| ''\---/'' | |
/// \ .-\__ `-` ___/-. /
/// ___`. .' /--.--\ `. . __
/// ."" '< `.___\_<|>_/___.' >'"".
/// | | : `- \`.;`\ _ /`;.`/ - ` : | |
/// \ \ `-. \_ __\ /__ _/ .-` / /
/// ======`-.____`-.___\_____/___.-`____.-'======
/// `=---='
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
/// Buddha Bless, No Bug !
///
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define ll long long
int t, m;
ll k, ans_n;
ll cal(ll n, int m)
{
if(n <
1)
return 0;
for(ll i = n +
1; ; i++
)
if(__gcd(n, i) ==
1)
{
m--
;
if(m ==
0)
return i - n;
/// (i - n) = (f(n, m) - n) = d
}
}
int main()
{
scanf("%d", &
t);
while(t--
)
{
scanf("%lld%d", &k, &
m);
ans_n = -
1;
for(
int d =
1; d <=
1000; d++
)
{
if(cal(k ^ d, m) ==
d)
{
if(ans_n == -
1)
ans_n = k ^
d;
else if(ans_n > (d ^ k))
/// ^ 运算的有优先度小于 < > == !=
ans_n = k ^
d;
}
}
printf("%lld\n", ans_n);
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11358647.html
