P7611 [THUPC2021] 幸运位置 题解

· · 题解

挺奇怪的一道题，虽然各种乱搞可过但还是很有思考价值的。

首先这道题有一个正经的构造做法，\gcd(a,b,c)>1 时直接判掉无解，设 \gcd(b,c)=x ，如果 x=1 ，那么 n=0 就满足条件。

否则我们可以发现 \gcd(a+b,x)=1 （因为有 \gcd(a,b,c)=1），由于一个数 x 满足 \gcd(x,y)=1,\gcd(x,z)=1 ，那么 \gcd(x,yz)=1 （可以反证），也就是说如果 \gcd(a+b,\frac{c}{x})=1 那么 n=1 就是答案。

考虑给 a+b 加上若干个 ax ，这样依然有 \gcd(kax+a+b,x)=1 ，现在是要找出一个 k 满足 \gcd(kax+a+b,\frac{c}{x})=1 ，发现是一个子问题，递归即可。由于 x>1 ，所以顶多递归 \log_2{c} 层（实际上平均只会递归两三层）。

有两个小问题，第一个是要保证子问题依然有解（不然一个有解的情况递归到无解的情况构造不出了）。考虑归纳证明只要 \gcd(a,b,c)=1 即有解，那么反证，假设有素数 p|\gcd(ax,a+b,c) ，那么一定有 p|a 或 p|x ，若 p|x ，则 p|b ，又因为 p|a+b ，所以又归到了 p|a 的情况，那么如果 p|a ，因为 p|a+b，所以 p|b ，因为 p|c ，所以 p|\gcd(a,b,c) 与前提矛盾。因此递归的任何一个子问题都是有解的。

第二个是解的大小的问题，注意到递归过程中所有 x 的乘积不超过 c ，那么最终结果的级别是 O(c) 的，看起来有可能会超过 10^{2000} ，但由于完全跑不满因此不会。

Code 1

from math import gcd
def solve(a,b,c):
    x=gcd(b,c)
    if x==1:
        return 0
    return solve(a*x,a+b,c//x)*x+1

for i in range(int(input())):
    a,b,c=map(int,input().split())
    if gcd(a,gcd(b,c))>1:
        print(-1)
        continue
    print(solve(a,b,c))

但是这道题直接从小到大枚举 n 或者随机化就可以过。虽然不会严谨的时间复杂度，但是是可以感性理解一下的。

具体来说，关键在于一个数的不同素因子的个数是在 O(\log c) 级别的，考虑用 c 的素因子个数对 n 的最小解进行感性分析。对于一个最小解 n'，也就是说 \forall n<n',\gcd(an+b,c)>1 ，取一个数 s 和素数 t 满足 s+t<n' ，假设 p|\gcd(sa+b,c),q|\gcd((s+t)a+b,c) ，如果 p=q ，那么有 p|ta ，明显 p\not|a ，否则 \gcd(a,b,c)>1 ，所以有 p|t ，限制 t 为素数，那么就有 p=t ，也就是说有 t|c 。

上述分析感性说明一下，就是对于一个间隔为素数的不满足条件的 n ，要么 p\neq q ，这样 c 就会分析出两个不同的素因子，要么 p=q ，这样这个间隔就是 c 的素因子，由于 c 的素因子本来就不会很多， n' 足够大时其中每一种素数间隔都会至少贡献一种不同的质因子，大胆猜测 n 的最小解也会是 O(\log c) 级别的，基于同样的思想我们也可以猜测随机化也只会期望猜 O(\log c) 次。

当然，上述只是一个非常不严谨的对最小解大小的猜测式的分析，大家看一看就行了。

Code 2

from math import gcd
for i in range(int(input())):
    a,b,c=map(int,input().split())
    if gcd(a,gcd(b,c))>1:
        print(-1)
        continue
    n=0
    while gcd(a*n+b,c)>1:
        n=n+1
    print(n)