一、题目
二、分析
题意就是找一个$n$满足题目中的公式,找不到就输出$-1$。
对于$${( f (n,m) – n )} \oplus {n} =k$$
可以转换一下变成$( f (n,m) – n ) = {k} \oplus {n}$,而对于$f (n,m) – n$可以打表看一下,根据质数密度可知很小。
由于异或相当于是一个不进位的加法,$f (n,m) – n$很小,相当于相当于$n$非常接近$k$。
枚举$n$,由于并没有卡时限,枚举范围很宽松。
三、AC代码
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 #define ll long long
5 #define Min(a,b) ((a)>(b)?(b):(a))
6 #define Max(a,b) ((a)>(b)?(a):(b))
7
8 ll gcd(ll a, ll b)
9 {
10 return b == 0 ? a : gcd(b, a % b);
11 }
12
13 ll f(ll n, int m)
14 {
15 int cnt = 0;
16 for(ll i = n + 1;;i++)
17 {
18 if(gcd(i, n) == 1)
19 {
20 cnt++;
21 }
22 if(cnt == m)
23 return i;
24 }
25 }
26
27 int main()
28 {
29 int T;
30 scanf("%d", &T);
31 while(T--)
32 {
33 int m;
34 ll k, n;
35 scanf("%lld %d", &k, &m);
36 for(n = Max(1, k - 1000); n < k + 1000; n++)
37 {
38 if( f(n, m) - n == (k^n) )
39 break;
40 }
41 if(n == k + 1000)
42 puts("-1");
43 else
44 printf("%lld\n", n);
45 }
46 return 0;
47 }