题解:HDU6641 TDL

题解:HDU6641 TDL

本题为 2019 HDU Multi-University Training Contest 6 的 1008 题

题目传送门🚪

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 $\mathrm{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)\oplus n$, where $\oplus$ denotes the bitwise XOR operation. Please write a program to find the smallest positive integer $n$ that $(f(n,m)−n)\oplus n=k$, or determine (whether) it is impossible.

Input

The first line of the input contains an integer $T$($1 \leq T \leq 10$), denoting the number of test cases.

In each test case, there are two integers $k,m$($1 \leq k\leq 10^{18}$,$1\leq m\leq100$).

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

1
2
3
2
3 5
6 100

Sample Output

1
2
5
-1

顺便吐槽下出题人的英语水平,“or determine it is impossible” 是什么鬼?

题意 & 题解

一道(对众多大佬来说比较水的)数论题,被拿来当签到题QAQ。

题目中,$(f(n,m) - n)\oplus n=k$,我们设 $d = f(n,m) - n$,则有 $d \oplus n = k$,两面同时异或上 $n\oplus k$,则有 $d \oplus n \oplus n \oplus k = k\oplus n \oplus k$ $\Rightarrow$ $n = d \oplus k$。$f(n,m)$ 表示大于 $n$ 的第 $m$ 大的与 $n$ 互质的数。由于 $m \leq 100$,一个奇数周围与它互质的数一般要多于与它不互质的数(举个例子,假设一个奇数 $9$,它周围有 $10$、$11$、$12$、$13$、$14$、$15$、$16$、$17$、$18$、$19$、$20$,其中与它互质的有$11$、$13$、$14$、$16$、$17$、$19$、$20$,要多于不与它互质的个数),所以我去枚举 $d$ 的值要优于枚举 $n$ 的值,况且一个数与它相邻的数一定是互质的,所以我们从 $1$ 开始枚举 $d$ 就可以了。枚举 $d$ 带入 $n = d \oplus p$ 得到的 $n$ 带回 $d=f(n,m)-n$ 中进行验证,如果成立,则代表这个结果是可行的。$f(n,m) = n + d$,$f(n,m)$ 满足与 $n$ 互质,即 $\mathrm{gcd}(f(n,m), n) = 1$,根据更相减损术,$\mathrm{gcd}(f(n,m) - n,n)$ $=$ $\mathrm{gcd}(f(n,m),n)$,所以枚举 $d$ 后通过判断 $d$ 与 $n$ 是否互质可以排除很多不满足的情况。而 $d$ 的枚举我们只需要枚举到第 $115$ 个质数,理由如下:

根据算术基本定理(唯一分解定理),任何一个大于 $1$ 的合数自然数 $N$,都可以分解成有限个质数的乘积,即:
$$
N = P_1^{a_{1}}P_2^{a_{2}}P_3^{a_{3}} \cdots P_n^{a_{n}}=\prod_{i=1}^nP_i^{a_i}
$$
根据约数个数定理,一个数的因数个数 $K$ 为:
$$
K = (a_1+1)(a_2+1)(a_3+1)\cdots(a_k+1)=\prod_{i=1}^n(a_i+1)
$$
最终结果 $n$ 不会超过long long的范围,而前 $16$ 个质数之积已经超过了long long的范围,也就是说,最小的一个可分解为 $15$ 个以上质数的数已经不符合要求了,所以最终结果 $n$ 最多有 $15$ 质数因数。而根据更相减损术,如果对于一个质数 $x$ 与一个自然数 $n$ 互质,则 $x$ 也与 $x+n$ 互质。如果我们根据算术基本定理对 $n$ 分解后它有 $15$ 个素数因数,那么第 $115$ 个素数(即 $631$)一定会是 $d$ 可以取到的极限了。所以 $d$ 只需要从 $1$ 枚举到 $631$,超出此范围就一定没有满足的结果了。

AC代码

来自同队的 zyg 大佬,感谢大佬!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std ;
typedef long long ll ;

ll gcd (ll x , ll y){
if (y==0) return x ;
else return gcd(y,x%y) ;
}
const ll maxn = 1e18+5 ;
int main(){
int t ;
scanf("%d",&t) ;
while(t--){
ll k ;
int m ;
ll ans = maxn ;
scanf("%lld %d",&k , &m) ;
for (ll i = 1; i <= 631 ; i++) { // 631是第115个质数
ll n = i^k ;
if (gcd(i,n)!=1) continue ;
int temp = 0 ;
for (ll j = 1 ; j< i ; j++) {
if (gcd(j,n)==1) temp++ ;
}
if (temp==m-1&&ans>n){
ans = n ;
}
}
if (ans == maxn) cout << -1 << endl ;
else cout << ans << endl ;
}
return 0 ;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×