JZTXT

7 月 30 日闲话

发布时间 2023-07-30 22:55:41作者: 冬日潮汐A

P9484 GCD

注意事项

  • 本题与节点数量无关
  • 设 \(gcd(i,j)=g\)，则 \(gcd(g,i)=g,gcd(g,j)=g\)，\(i-g\)，\(j-g\) 之间必定有连边
  • 如果使用更小的公约数 \(g'\)，答案必定更差
  • 答案为 \((i-g)+(j-g)=i+j-2 \times gcd(i,j)\)

特别注意事项

  • 本题时限 500ms，需要 int 快读快写，具体代码见 OI 常用模板。

（为什么这点东西也能水一篇闲话）