题解:HDU6641 TDL

发布于 / 题解 / 0 条评论

本题为 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

2
3 5
6 100

Sample Output

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 kf(n,m) 表示大于 n 的第 m 大的与 n 互质的数。由于 m \leq 100,一个奇数周围与它互质的数一般要多于与它不互质的数(举个例子,假设一个奇数 9,它周围有 1011121314151617181920,其中与它互质的有11131416171920,要多于不与它互质的个数),所以我去枚举 d 的值要优于枚举 n 的值,况且一个数与它相邻的数一定是互质的,所以我们从 1 开始枚举 d 就可以了。枚举 d 带入 n = d \oplus p 得到的 n 带回 d=f(n,m)-n 中进行验证,如果成立,则代表这个结果是可行的。f(n,m) = n + df(n,m) 满足与 n 互质,即 \mathrm{gcd}(f(n,m), n) = 1,根据更相减损术\mathrm{gcd}(f(n,m) – n,n) = \mathrm{gcd}(f(n,m),n),所以枚举 d 后通过判断 dn 是否互质可以排除很多不满足的情况。而 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 大佬,感谢大佬!

#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 ;
}
转载原创文章请注明,转载自: KONGJUNE » 题解:HDU6641 TDL
Not Comment Found