自动搬运

查看原文

来自洛谷，原作者为

	yyyyxh OI 是啥 (O_o)？

搬运于2025-08-24 22:31:32，当前版本为作者最后更新于2022-03-12 09:54:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先这道题有一个正经的构造做法，$\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)