？？
这命题是错的吧。
11%7=4,4>7/2。
by CDFLS_mao_zx @ 2020-10-27 15:24:31
对于任何数$n,q$有 $n\bmod q<\dfrac{n}{2}$。
所以$gcd$这东西是$log$的。
by CDFLS_mao_zx @ 2020-10-27 15:25:47
@[CDFLS_mao_zx](/user/177535) 前提条件 $q \leq n$ 吧
by 素质玩家孙1超 @ 2020-10-27 15:27:03
嗯嗯
by CDFLS_mao_zx @ 2020-10-27 16:23:14
@[CDFLS_mao_zx](/user/177535) 如果q≤n 为什么呢
by 低熵体 @ 2020-10-27 19:52:44
@[低熵体](/user/116683) 额，我证明下。
by CDFLS_mao_zx @ 2020-10-27 19:58:38
1:
$q\leq\dfrac{n}{2}$
模数小于$\dfrac{n}{2}$，显然。
2:
$q>\dfrac{n}{2}$
$n \mod q=n-q$
$\therefore n \mod q \leq \dfrac{n}{2}$
by CDFLS_mao_zx @ 2020-10-27 20:02:35
@[CDFLS_mao_zx](/user/177535) 啊好的非常感谢
by 低熵体 @ 2020-10-27 20:07:59