[数论]TDL

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.
1≤k≤10¹⁸,1≤m≤100.

分析

看起来很吓人其实...的题.
f(n,m)是比n大的第m个与n互素的数.所以f(n,1)=n+1,因为n+1是第一个比n大且与n互素的数.如果f(n,2)=n+x,那么x一定是从1开始(包括1)第2个与n互质的数,这是因为如果n+x与n互质,那么x就与n互质,如果1~x之间还有其他的与n互质的数y,那么f(n,2)就不是n+x了(而可能是n+y).
所以f(n,m)-n就是从1开始(包括1)第m个与n互质的数.设f(n,m)-n=t.我们断言t<700.这一判断的依据是:对于一个10¹⁸数量级的数来说,第100个与它互素的数不超过700.
这个论断是这么来的:第120个质数是659,在这120个质数里面,不与n互质的至多有20个,否则n的不同的素因子将至少有20个,而20!已经远远超过10¹⁸了,所以这120个质数里面至少有100个与n互质.所以700以内至少有100个与n互质的数.
所以我们从1到700枚举t,这样得到n=t⊕k,然后再检验第m个与n互素的数是否真的是t,直接暴力算出(枚举1到700)第m个与n互质的数就好了.