题意 给定      n    n   n 个正整数，求两两     <mtext> lcm </mtext>   \text{lcm}   lcm 的最大值。 所有输入在     [   1   ,   1    0   5    ]    [1,10^5]   [1,105]范围内。 分析 首先枚举      gcd   ⁡   =   g    \gcd = g   gcd=g，那么将数组中      g    g   g 的倍数都拿出来。 问题转化为，在数组中找两个互质的数，使他们的积尽量大。 我们将这些数从大到小枚举，那么枚举到一个数      x    x ...

简介      F   F   T    FFT   FFT （法法塔）是个什么玩意？他的全名叫快速傅里叶变换（然而貌似和傅里叶并没有太大关系），用来快速求出多项式的点值表示，这个东西一般用来解决多项式相乘的问题。 一般的高精度乘法，我们有个      O   (    n   2    )    O(n^2)   O(n2) 的普及组做法，然而这个做法远远不能满足现代小学生的需求（传言小学生都会FFT）。于是我们要学习更优复杂度的做法，那就是复杂度为      O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn) 的      F   F ...

题意      n    n   n 个人，      p    p   p 个位置，选      p    p   p 人作为每个位置的运动员，再选      k    k   k 个作为观众。 每个人作为运动员在每个位置的权值       s    i   ,   p      s_{i,p}   si,p​ 和每个人作为观众权值       a   i     a_i   ai​ 已知。      n   ≤   100000   ,   p   ≤   7    n\leq 100000, p \leq 7   n≤100000,p≤7 分析 这题并不难想，可惜比赛时没时间了QAQ 首...

题意 求      (    a   1    +    a   2    )   ⊕   (    a   1    +    a   3    )   ⊕   …   ⊕   (    a   1    +    a   n    )   ⊕   (    a   2    +    a   3    )   ⊕   …   ⊕   (    a   2    +    a   n    )   …   ⊕   (    a    n   −   1     +    a   n    )    (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \o...

题意      T    T   T 组数据，每组数据给出一个      2   N    2N   2N 个点的二分图，给出右边      n    n   n 个点的权值，设      f   (   S   )    f(S)   f(S) 表示所有与左边集合      S    S   S 有连边的右边点的点权和。求      f   (   S   )    f(S)   f(S) 的      gcd   ⁡    \gcd   gcd。 分析 对于右边的点：  如果没有连边，则可以删去 如果有连边情况相同的点，则合并在一起，权值相加  这样，最终得到的是若干个点，每个点对应左边不...

题意 给定一个数组      {    a   i    }    \{a_i\}   {ai​}，求最少的数的个数，使得它们的乘积为平方数。 其中，      a   i     a_i   ai​ 的因子不超过      7    7   7 个      n   ≤   1    0   5    ,    a   i    ≤   1    0   6     n\leq 10^5, a_i \leq 10^6   n≤105,ai​≤106 分析 设       a   i    =  <munder>  ∏   j  </munder>   p   j   ...

题意 求出一个大于      ⌈    n    ⌉    \lceil\sqrt{n}\rceil   ⌈n ​⌉ 的环或找出      ⌈    n    ⌉    \lceil\sqrt{n}\rceil   ⌈n ​⌉ 个点的独立集。 分析 用      d   f   s    dfs   dfs 树可以找最大环。      d   f   s    dfs   dfs 树是什么？就是从某个点进行      d   f   s    dfs   dfs 形成的树，如图。  深色的是树边，浅色的是非树边。      d   f   s    dfs   dfs 树有个性质：每条非树边 ...

题意 给出一个排列      {    p   i    }    \{p_i\}   {pi​}，同时给出一个炸弹顺序      {    q   i    }    \{q_i\}   {qi​}，第      i    i   i 颗炸弹放在第       q   i     q_i   qi​ 处。每次从左往右加入       p   i     p_i   pi​，遇到炸弹时炸掉当前最大值。输出放前      i    i   i 颗炸弹最终序列的最大值（     i   =   0   ,   1   ,   2...   ,   n   −   1    i=0,1,2...,n...

题意 有      n    n   n 个位置，现在要往上面填数，给定      k    k   k，每个数小于       2   k     2^k   2k。现在有      m    m   m 个限制条件，每个限制条件给定       l   i    ,    r   i    ,    x   i     l_i,r_i,x_i   li​,ri​,xi​，要求满足      a   [    l   i    ]   &   a   [    l   i    +   1   ]   &   …   &   a   [    r   i    ]  ...

题目描述   分析 先吐槽一波，为什么 latex 不能复制！！！！ 好了让我们看看这道题。 设       s   i     s_i   si​ 为前      i    i   i 个玩具的长度前缀和，设       f   i     f_i   fi​ 表示前      i    i   i 个玩具的最小费用，于是有一个显然的转移方程：       f   i    =   m   i   n   {    f    j   −   1     +   (   i   −   j   +    s   i    −    s    j   −   1     −   L    )  ...

题意 有一个      n   ∗   m    n*m   n∗m 的矩阵，每次可以往一个格子      +   2    +2   +2，或在任意相邻的两个格子      +   1    +1   +1，可以操作无限次。给定一个限制      [   L   ,   R   ]    [L,R]   [L,R]，问有多少种初始情况满足       a    i   ,   j     ∈   [   L   ,   R   ]    a_{i,j}\in[L,R]   ai,j​∈[L,R]，使得经过若干次操作后所有格子高度相等。 分析 日常感叹我太弱了。。。 首先，由于有      +...

题意      [   1   ,   n   ]    [1,n]   [1,n] 中，任选      k    k   k 个数，求两两      g   c   d    gcd   gcd 的最大值的最小值。 分别对      k   =   2   ,   3   ,   .   .   .   ,   n    k=2,3,...,n   k=2,3,...,n 求取答案。      n   ≤   500000    n\leq 500000   n≤500000 分析 一个数      x    x   x 放入集合时，它的所有因子一定都在集合中。否则，我们可以用它的某一个因子...

题意 给定一个数      D    D   D，由      D    D   D 生成以下图：  每个点都为      D    D   D 的因子      x    x   x 和      y    y   y 连有无向边边当且仅当      x   ∣   y    x|y   x∣y 且       y   x     \frac{y}{x}   xy​ 为素数      (   x   ,   y   )    (x,y)   (x,y) 的边权值为能整除      x    x   x 但不能整除      y    y   y 的数的个数  有      q    q   ...

什么是阶 若      (   a   ,   m   )   =   1    (a,m)=1   (a,m)=1，则使       a   l    ≡   1  <mtext>   </mtext>  (   m   o   d  <mtext>   </mtext>  m   )    a^l\equiv1~(mod~m)   al≡1 (mod m) 的最小      l    l   l，称之为      a    a   a 关于模      m    m   m 的阶，记为      o   r    d   m    a    ...