【Codeforces338D】GCD Table


题意

给出一张 \(n\times m\) 的表格,表格的第 \(i\) 行,第 \(j\) 列为 \(gcd(i,j)\) ,现在给出一个长度为 \(k\) 的数列,询问是否是矩阵中某一行连续的一部分。

分析

因为对于所有的 \(a_i\) 都有 \(gcd(x,y+i-1)=a_i\) ,也就是 \(a_i|x\) ,那么 \(x\) 至少是 \(lcm(a_1,a_2,\cdots ,a_k)\) 。

又因为 \(a_i|(y+i-1)\) ,所以有 \(y\equiv 1-i(mod \; a_i)\) ,于是我们可以通过解 \(k\) 个线性同余方程组求得一个最小的正整数 \(y\) 。

显然此时我们求得的一个可能解 \(x=x_0=lcm(a_1,a_2,\cdots ,a_k),y=y_0\) 是最小的。

对于任意一个数 \(a_i=gcd(x,y)\) ,如果我们增大 \(x\) 或者 \(y\) ,显然必须满足 \(x=x\cdot t_1\) 或者 \(y=y+x_0t_2\) ,而显然,这样的变化只会让 \(gcd(x,y)\) 不变或者变大,于是我们知道,如果 \(x=x_0=lcm(a_1,a_2,\cdots ,a_k),y=y_0\) 是不合法的,显然通过变化得到的 \(x,y\) 也不会合法。

上面推导得到 \(x,y\) 的解显然只满足必要性,所以我们必须要对结果进行验证。

在合并线性方程的过程中,需要用到慢速乘。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,990

Categories

Archive

Comments