题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6641

题目：

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 ``-?'' instead.

Sample Input

2 

3 5

6 100

Sample Output

5 

-1

解题思路：

可以拿程序跑一下就能推测出：比n大且和n的gcd值=1的数相邻得比较紧密，f(n,100)-n不是很大，只有几百左右（有人说最多五百多），即然不知道准确的数是多少，那就定f(n,100)-n最大是1000吧。

 令, 那么,下面只需要根据这个n求得,验证是否满足这个等式即可，去满足条件的最小的n。

⚠️ 可能是0，要特判一下！

最坏的时间复杂度：O(1000 * 100 *T)=O(1e6)

 

ac代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1000000;
ll k;
int M, t;
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool judge(ll n)
{
    ll x = n;
    int m = M;
    while(m)
    {
        x++;//退出循环时x表示f(n,m)
        if(gcd(x, n) == 1)
            m--;
    }
    if(((x-n)^n) == k) return true; // (f(n, m)- n) ^ n == k ?
    else return false;

}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld %d", &k, &M);
        ll ans = -1;
        //f(1000,100)=1249
        for(ll i = 1; i < 1000; i++) //枚举f(n,m)-n
        {
            ll n = i^k; // n = （f(n,m)-n)^k
            if(n && judge(n)) // 判断这个n是否满足等式
            {
                if(ans == -1) ans = n;
                else ans = min(ans, n); // 更新最小值
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}