1 条题解

  • 0
    @ 2026-11-15 12:28:17

    题解:互质划分(coprime)

    n≤10n\leq 10 的数据可以搜索来解决。

    当 n=1n=1 时划分为一堆。当 n>1n>1 时把 2i−1,2i2i-1,2i 划分为一堆,若 nn 是奇数则把 nn 划入最后一堆。相邻的两个正整数互质,相邻的三个正整数 2i−1,2i,2i+12i-1,2i,2i+1 也是互质的,因为 gcd⁡(2i−1,2i+1)=gcd⁡(2i−1,2)=1\gcd(2i-1,2i+1)=\gcd(2i-1,2)=1,所以可以划分为 ⌊n2⌋\lfloor \frac{n}{2}\rfloor 堆,并且 22 的倍数共有 ⌊n2⌋\lfloor \frac{n}{2}\rfloor 个,每两个都不能在同一组,于是是最少的堆数。

    • 1

    信息

    ID
    40
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者