[Codeforces] number theory (R1600) Part.7

题单:https://codeforces.com/problemset/page/1?tags=number+theory%2C1201-1600

1113B. Sasha and Magnetic Machines

原题指路:https://codeforces.com/problemset/problem/1113/B

题意

给定一个长度为 n    ( 2 ≤ n ≤ 5 e 4 ) n\ \ (2\leq n\leq 5\mathrm{e}4) n  (2≤n≤5e4)的序列 a 1 , ⋯   , a n    ( 1 ≤ a i ≤ 100 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 100) a1​,⋯,an​  (1≤ai​≤100).现有操作:选择一对 a i a_i ai​和 a j a_j aj​,选择 a i a_i ai​的一个约数 x x x,令 a i / = x , a j ∗ = x a_i/=x,a_j*=x ai​/=x,aj​∗=x.问经过至多一次操作后得到的序列的元素之和的最小值.

思路

为使得序列元素之和最小,约数 x x x应乘在序列的最小元素上.因至多进行一次操作,枚举每个 a i a_i ai​进行操作即可.

代码

void solve() {
  int n; cin >> n;
  vi a(n);
  for (auto& ai : a) cin >> ai;

  int minnum = *min_element(all(a));
  int sum = accumulate(all(a), 0);
  int ans = sum;

  for (auto ai : a) {
    for (int d = 1; d <= ai; d++) {
      if (ai % d == 0) {
        int res = sum - minnum - ai;
        res += minnum * d + ai / d;
        ans = min(ans, res);
      }
    }
  }
  cout << ans;
}

int main() {
  solve();
}

---

---

1133D. Zero Quantity Maximization

原题指路:https://codeforces.com/problemset/problem/1133/D

题意 ( 2   s 2\ \mathrm{s} 2 s)

给定两长度为 n    ( 1 ≤ n ≤ 2 e 5 ) n\ \ (1\leq n\leq 2\mathrm{e}5) n  (1≤n≤2e5)的序列 a 1 , ⋯   , a n a_1,\cdots,a_n a1​,⋯,an​和 b 1 , ⋯   , b n    ( − 1 e 9 ≤ a i , b i ≤ 1 e 9 ) b_1,\cdots,b_n\ \ (-1\mathrm{e}9\leq a_i,b_i\leq 1\mathrm{e}9) b1​,⋯,bn​  (−1e9≤ai​,bi​≤1e9).现按如下方式构造一个长度为 n n n的序列 c [ ] c[] c[]:选定一个实数 d d d,令 c i = d ⋅ a i + b i    ( 1 ≤ i ≤ n ) c_i=d\cdot a_i+b_i\ \ (1\leq i\leq n) ci​=d⋅ai​+bi​  (1≤i≤n).求 c [ ] c[] c[]中 0 0 0的个数的最大值.

思路

①若 a i = 0 a_i=0 ai​=0,则 d d d的选择对答案无影响,只需检查 b i b_i bi​是否为 0 0 0即可.

②若 a i ≠ 0 a_i\neq 0 ai​=0,应取 d = − b i a i d=-\dfrac{b_i}{a_i} d=−ai​bi​​.将分数化为最简分数后,记录其出现的次数,最后 d d d取出现次数最多的分数即可.

代码

map<pii, int> cnt;

void norm(pii& x) {
  if (!x.first) {
    x.first = 0, x.second = 1;
    return;
  }

  if (x.first / abs(x.first) * x.second / abs(x.second) < 0)
    x.first = -abs(x.first), x.second = abs(x.second);
  else x.first = abs(x.first), x.second = abs(x.second);

  int g = abs(gcd(x.first, x.second));
  x.first /= g, x.second /= g;
}

void solve() {
  int n; cin >> n;
  vi a(n), b(n);
  for (auto& ai : a) cin >> ai;
  for (auto& bi : b) cin >> bi;

  int cnt0 = 0;  // 0的个数
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] == 0) cnt0 += !b[i];
    else{
      pii d = { -b[i],a[i] };
      norm(d);
      ans = max(ans, ++cnt[d]);
    }
  }
  cout << cnt0 + ans;
}

int main() {
  solve();
}

---

---

1155C. Alarm Clocks Everywhere

原题指路:https://codeforces.com/problemset/problem/1155/C

题意 ( 3   s 3\ \mathrm{s} 3 s)

给定一长度为 n    ( 2 ≤ n ≤ 3 e 5 ) n\ \ (2\leq n\leq 3\mathrm{e}5) n  (2≤n≤3e5)的序列 x 1 , ⋯   , x n    ( 1 ≤ x i ≤ 1 e 18 ) x_1,\cdots,x_n\ \ (1\leq x_i\leq 1\mathrm{e}18) x1​,⋯,xn​  (1≤xi​≤1e18)和一长度为 m    ( 1 ≤ m ≤ 3 e 5 ) m\ \ (1\leq m\leq 3\mathrm{e}5) m  (1≤m≤3e5)的序列 p 1 , ⋯   , p m    ( 1 ≤ p i ≤ 1 e 18 ) p_1,\cdots,p_m\ \ (1\leq p_i\leq 1\mathrm{e}18) p1​,⋯,pm​  (1≤pi​≤1e18).构造一个等差数列,使得其首项 y ∈ Z y\in\mathbb{Z} y∈Z,公差 ∈ p [ ] \in p[] ∈p[],且 x [ ] x[] x[]中的所有数都是等差数列中的项.若有解,第一行输出"YES",第二行输出任一组首项和公差的下标;否则输出"NO".

思路

显然可取 y = x i y=x_i y=xi​.考察 x [ ] x[] x[]的差分序列 d i f f [ ] diff[] diff[],则公差 p p p需为所有 d i f f i diff_i diffi​的约数.

代码

void solve() {
  int n, m; cin >> n >> m;
  vl x(n), p(m);
  for (auto& xi : x) cin >> xi;
  for (auto& pi : p) cin >> pi;

  ll g = x[1] - x[0];  // 序列x[]的差分序列的gcd
  for (int i = 2; i < n; i++) g = gcd(g, x[i] - x[i - 1]);

  for (int i = 0; i < m; i++) {
    if (g % p[i] == 0) {
      cout << "YES" << endl;
      cout << x[0] << ' ' << i + 1;
      return;
    }
  }
  cout << "NO";
}

int main() {
  solve();
}

---

---

1165D. Almost All Divisors

原题指路:https://codeforces.com/problemset/problem/1165/D

题意 ( 2   s ) (2\ \mathrm{s}) (2 s)

有 t    ( 1 ≤ t ≤ 25 ) t\ \ (1\leq t\leq 25) t  (1≤t≤25)组测试数据.每组测试数据给定一个长度为 n n n的序列 d 1 , ⋯   , d n    ( 2 ≤ d i ≤ 1 e 6 ) d_1,\cdots,d_n\ \ (2\leq d_i\leq 1\mathrm{e}6) d1​,⋯,dn​  (2≤di​≤1e6),表示某数 x x x的所有非平凡约数,其中 d i d_i di​两两相异.若存在这样的数 x x x,输出 x x x;否则输出 − 1 -1 −1.

思路

对数 x x x,若存在约数 d d d,则也存在约数 n d \dfrac{n}{d} dn​,则 d [ ] d[] d[]中最小元素与最大元素之积即 x x x.因 x x x的约数一定,则原序列 d [ ] d[] d[]是 x x x的非平凡约数序列的某个排列,将它们排序后判断是否相等即可.

代码

void solve() {
  int n; cin >> n;
  vl d(n);
  for (auto& di : d) cin >> di;

  sort(all(d));
  ll x = (ll)d[0] * d[n - 1];

  vl divisors;
  for (int d = 2; (ll)d * d <= x; d++) {
    if (x % d == 0) {
      divisors.push_back(d);
      if (d != x / d) divisors.push_back(x / d);
    }
  }
  sort(all(divisors));
  cout << (d == divisors ? x : -1) << endl;
}

int main() {
  CaseT  // 单测时注释掉该行
    solve();
}

---

---

1174C. Ehab and a Special Coloring Problem

原题指路:https://codeforces.com/problemset/problem/1174/C

题意

给定一个整数 n    ( 2 ≤ n ≤ 1 e 5 ) n\ \ (2\leq n\leq 1\mathrm{e}5) n  (2≤n≤1e5).构造一个序列$a_2,\cdots,a_n\ \ (1\leq a_i\leq n)\ s.t.\ 对 对 对\forall i\in[2,n] , 若 ,若 ,若\gcd(i,j)=1 , 则 ,则 ,则a_i\neq a_j , 且 ,且 ,且a[]$的最大值最小.

思路

显然可让每个数与其最小素因子取值相等,且每个素因子下标的 a [ i ] a[i] a[i]应取尽量小的不相等的数.类似于筛法的过程染色即可.

代码

const int MAXN = 1e5 + 5;
int ans[MAXN], idx;

void solve() {
  int n; cin >> n;

  for (int i = 2; i <= n; i++) {
    if (!ans[i]) {
      ans[i] = ++idx;
      for (int j = 2 * i; j <= n; j += i) ans[j] = ans[i];
    }
    cout << ans[i] << ' ';
  }
}

int main() {
  solve();
}

---

---

1178D. Prime Graph

原题指路:https://codeforces.com/problemset/problem/1178/D

题意

给定一个整数 n n n,构造一个包含 n n n个节点的简单无向图(无重边无自环),要求边数为素数,每个节点的度数也为素数.

如下图,图 1 1 1和图 3 3 3是 n = 4 n=4 n=4时的合法解,而图 2 2 2不是.

第一行输入一个整数 n    ( 3 ≤ n ≤ 1000 ) n\ \ (3\leq n\leq 1000) n  (3≤n≤1000).

若无解,则输出 − 1 -1 −1;否则第一行输出一个素数 m    ( 2 ≤ m ≤ n ( n − 1 ) 2 ) m\ \ \left(2\leq m\leq \dfrac{n(n-1)}{2}\right) m  (2≤m≤2n(n−1)​),表示边数.接下来 m m m行每行输出两个整数 u , v    ( 1 ≤ u , v ≤ n ) u,v\ \ (1\leq u,v\leq n) u,v  (1≤u,v≤n),表示节点 u u u与 v v v间存在无向边.若有多组解,输出任一组.

思路

一定有解,下面给出构造:

① n = 3 n=3 n=3时,三角形是唯一解.

② n ≥ 4 n\geq 4 n≥4时,先构造一个环 1 ↔ 2 ↔ ⋯ ↔ n ↔ 1 1\leftrightarrow 2\leftrightarrow \cdots\leftrightarrow n\leftrightarrow 1 1↔2↔⋯↔n↔1,此时每个节点的度数都为 2 2 2,但边数 n n n可能非素数.

​ 若此时 n n n非素数,设 n n n的下一个素数为 m m m,则只需对任意 i ∈ [ 1 , m − n ] i\in[1,m-n] i∈[1,m−n],加一条边 i ↔ ( i + n 2 ) i\leftrightarrow \left(i+\dfrac{n}{2}\right) i↔(i+2n​).

代码

bool check(int n) {  // 判断素数
  for (int i = 2; i * i <= n; i++) 
    if (n % i == 0) return false;
  return true;
}

void solve() {
  int n; cin >> n;

  int m = n;
  while (!check(m)) m++;

  cout << m << endl;
  for (int i = 1; i < n; i++) cout << i << ' ' << i + 1 << endl;
  cout << "1 " << n << endl;

  for (int i = 1; i <= m - n; i++) cout << i << ' ' << i + n / 2 << endl;
}

int main() {
  solve();
}

---

---

1195D1. Submarine in the Rybinsk Sea (easy edition)

原题指路:https://codeforces.com/problemset/problem/1195/D1

题意 ( 2   s 2\ \mathrm{s} 2 s)

给定两个整数的十进制表示(无前导零) a 1 , ⋯   , a p a_1,\cdots,a_p a1​,⋯,ap​和 b 1 , ⋯   , b q b_1,\cdots,b_q b1​,⋯,bq​.定义函数 f ( a 1 , ⋯   , a p , b 1 , ⋯   , b q ) = { a 1 a 2 ⋯ a p − q + 1 b 1 a p − q + 2 b 2 ⋯ a p − 1 b q − 1 a p b q , p ≥ q b 1 b 2 ⋯ b q − p a 1 b q − p + 1 a 2 ⋯ a p − 1 b q − 1 a p b q f(a_1,\cdots,a_p,b_1,\cdots,b_q)=\begin{cases}a_1a_2\cdots a_{p-q+1} b_1 a_{p-q+2}b_2\cdots a_{p-1} b_{q-1}a_p b_q,p\geq q \\ b_1b_2 \cdots b_{q-p} a_1 b_{q-p+1}a_2\cdots a_{p-1}b_{q-1}a_p b_q\end{cases} f(a1​,⋯,ap​,b1​,⋯,bq​)={a1​a2​⋯ap−q+1​b1​ap−q+2​b2​⋯ap−1​bq−1​ap​bq​,p≥qb1​b2​⋯bq−p​a1​bq−p+1​a2​⋯ap−1​bq−1​ap​bq​​.如 f ( 1111 , 2222 ) = 12121212 , f ( 7777 , 888 ) = 7787878 , f ( 111 , 2222 ) = ( 2121212 ) f(1111,2222)=12121212,f(7777,888)=7787878,f(111,2222)=(2121212) f(1111,2222)=12121212,f(7777,888)=7787878,f(111,2222)=(2121212).

给定一个长度为 n    ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n  (1≤n≤1e5)的序列 a 1 , ⋯   , a n    ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1​,⋯,an​  (1≤ai​≤1e9),其中每个 a i a_i ai​的十进制表示(无前导零)等长.求 ∑ i = 1 n ∑ j = 1 n f ( a i , a j ) \displaystyle \sum_{i=1}^n \sum_{j=1}^n f(a_i,a_j) i=1∑n​j=1∑n​f(ai​,aj​),答案对 998244353 998244353 998244353取模.

思路

显然有 f ( a i , a j ) f(a_i,a_j) f(ai​,aj​)也会有 f ( a j , a i ) f(a_j,a_i) f(aj​,ai​).因每个 a i a_i ai​的十进制表示等长,注意到 f ( a 1 ⋯ a p , b 1 ⋯   , b p ) = a 1 b 1 a 2 b 2 ⋯ b p b p , f ( b 1 ⋯   , b p , a 1 ⋯ a p ) = b 1 a 1 b 2 a 2 ⋯ b p a p f(a_1\cdots a_p,b_1\cdots,b_p)=a_1b_1a_2b_2\cdots b_pb_p,f(b_1\cdots,b_p,a_1\cdots a_p)=b_1a_1b_2a_2\cdots b_p a_p f(a1​⋯ap​,b1​⋯,bp​)=a1​b1​a2​b2​⋯bp​bp​,f(b1​⋯,bp​,a1​⋯ap​)=b1​a1​b2​a2​⋯bp​ap​,即 f ( a i , a j ) + f ( a j , a i ) = f ( a i , a i ) + f ( a j , a j ) f(a_i,a_j)+f(a_j,a_i)=f(a_i,a_i)+f(a_j,a_j) f(ai​,aj​)+f(aj​,ai​)=f(ai​,ai​)+f(aj​,aj​),则 ∑ i = 1 n ∑ j = 1 n f ( a i , a j ) = n ∑ i = 1 n f ( a i , a i ) \displaystyle \sum_{i=1}^n \sum_{j=1}^n f(a_i,a_j)=n\sum_{i=1}^n f(a_i,a_i) i=1∑n​j=1∑n​f(ai​,aj​)=ni=1∑n​f(ai​,ai​).

代码

const int MOD = 998244353;

void solve() {
  int n; cin >> n;

  int ans = 0;
  for (int i = 0; i < n; i++) {
    string s; cin >> s;
    int len = s.length();
    int cur = 0;
    for (int i = 0; i < len; i++) {
      cur = ((ll)cur * 10 + s[i] - '0') % MOD;
      cur = ((ll)cur * 10 + s[i] - '0') % MOD;
    }
    ans = (ans + cur) % MOD;
  }

  ans = (ll)ans * n % MOD;
  cout << ans;
}

int main() {
  solve();
}

---

---

1200C. Round Corridor

原题指路:https://codeforces.com/problemset/problem/1200/C

题意

双层圆形空间分为若干个房间,内层等分为 n n n部分,相邻两部分间有墙;外层等分为 m m m部分,相邻两部分间有墙.如下图为 n = 4 , m = 6 n=4,m=6 n=4,m=6时的房间分布:

现有 q q q个询问,每个询问输入四个整数 s x , s y , e x , e y    ( 1 ≤ s x , e x ≤ 2 ) s_x,s_y,e_x,e_y\ \ (1\leq s_x,e_x\leq 2) sx​,sy​,ex​,ey​  (1≤sx​,ex​≤2),若 s x = 1 s_x=1 sx​=1,则 s y ∈ [ 1 , n ] s_y\in[1,n] sy​∈[1,n];否则 s y ∈ [ 1 , m ] s_y\in[1,m] sy​∈[1,m], e y e_y ey​的范围同理,表示询问是否能从房间 ( s x , s y ) (s_x,s_y) (sx​,sy​)走到 ( e x , e y ) (e_x,e_y) (ex​,ey​),若能则输出"YES";否则输出"NO".

第一行输入三个整数 n , m , q    ( 1 ≤ n , m ≤ 1 e 18 , 1 ≤ q ≤ 1 e 4 ) n,m,q\ \ (1\leq n,m\leq 1\mathrm{e}18,1\leq q\leq 1\mathrm{e}4) n,m,q  (1≤n,m≤1e18,1≤q≤1e4).接下来 q q q行每行输入四个整数 s x , s y , e x , e y    ( 1 ≤ s x , e x ≤ 2 ) s_x,s_y,e_x,e_y\ \ (1\leq s_x,e_x\leq 2) sx​,sy​,ex​,ey​  (1≤sx​,ex​≤2),若 s x = 1 s_x=1 sx​=1,则 s y ∈ [ 1 , n ] s_y\in[1,n] sy​∈[1,n];否则 s y ∈ [ 1 , m ] s_y\in[1,m] sy​∈[1,m], e y e_y ey​的范围同理,表示一个询问.

思路

墙的位置 ( 1 , 1 n ) , ( 1 , 2 n ) , ⋯   , ( 1 , n n ) , ( 2 , 1 m ) , ( 2 , 2 m ) , ⋯   , ( 2 , m m ) \left(1,\dfrac{1}{n}\right),\left(1,\dfrac{2}{n}\right),\cdots,\left(1,\dfrac{n}{n}\right),\left(2,\dfrac{1}{m}\right),\left(2,\dfrac{2}{m}\right),\cdots,\left(2,\dfrac{m}{m}\right) (1,n1​),(1,n2​),⋯,(1,nn​),(2,m1​),(2,m2​),⋯,(2,mm​).对某个分数 x x x,若同时有墙 ( 1 , x ) (1,x) (1,x)和 ( 2 , x ) (2,x) (2,x),则无法从房间 y < x y<x y<x到房间 z > x z>x z>x.

设 g = gcd ⁡ ( n , m ) g=\gcd(n,m) g=gcd(n,m),则内外层同时有墙的位置为 1 g , 2 g , ⋯   , g g \dfrac{1}{g},\dfrac{2}{g},\cdots,\dfrac{g}{g} g1​,g2​,⋯,gg​,这些墙将空间分为 g g g个部分,每个部分内部可互相到达,不同部分不能互相到达.

① x = 1 x=1 x=1时, ( 1 , 1 ) , ( 1 , 2 ) , ⋯   , ( 1 , n g ) \left(1,1\right),\left(1,2\right),\cdots,\left(1,\dfrac{n}{g}\right) (1,1),(1,2),⋯,(1,gn​)属于第一组; ( 1 , n g + 1 ) , ( 1 , n g + 2 ) , ( 1 , 2 n g ) \left(1,\dfrac{n}{g}+1\right),\left(1,\dfrac{n}{g}+2\right),\left(1,\dfrac{2n}{g}\right) (1,gn​+1),(1,gn​+2),(1,g2n​)属于第二组; ⋯ \cdots ⋯.

② x = 2 x=2 x=2时, ( 2 , 1 ) , ( 2 , 1 ) , ⋯   , ( 2 , m g ) (2,1),(2,1),\cdots,\left(2,\dfrac{m}{g}\right) (2,1),(2,1),⋯,(2,gm​)属于第一组; ( 2 , m g + 1 ) , ( 2 , m g + 2 ) , ⋯   , ( 2 , 2 m g ) \left(2,\dfrac{m}{g}+1\right),\left(2,\dfrac{m}{g}+2\right),\cdots,\left(2,\dfrac{2m}{g}\right) (2,gm​+1),(2,gm​+2),⋯,(2,g2m​)属于第二组; ⋯ \cdots ⋯.

代码

void solve() {
  ll n, m; cin >> n >> m;

  ll g = gcd(n, m);
  CaseT{
    ll sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey;
    sy--, ey--;

    if (sx == 1) sy /= n / g;
    else sy /= m / g;
    if (ex == 1) ey /= n / g;
    else ey /= m / g;
    cout << (sy == ey ? "YES" : "NO") << endl;
  }
}

int main() {
  solve();
}

---

---

1209B. Koala and Lights

原题指路:https://codeforces.com/problemset/problem/1209/B

题意

编号 1 ∼ n 1\sim n 1∼n的 n n n盏灯排成一排,每盏灯有打开和关闭两种状态,其中 i i i号灯有两个参数 a i , b i a_i,b_i ai​,bi​,表示它会在 b i , b i + a i , b i + 2 a i , ⋯ b_i,b_i+a_i,b_i+2a_i,\cdots bi​,bi​+ai​,bi​+2ai​,⋯时刻反转状态.经过充分长的时间,求每个时刻打开的灯的数量的最大值.

第一行输入一个整数 n    ( 1 ≤ n ≤ 100 ) n\ \ (1\leq n\leq 100) n  (1≤n≤100).第二行输入一个长度为 n n n的 0 − 1 0-1 0−1串,其中第 i i i个字符为 0 0 0表示初始时 i i i号灯关闭,为 1 1 1表示初始时 i i i号灯打开.接下来 n n n行每行输入两个整数 a , b    ( 1 ≤ a , b ≤ 5 ) a,b\ \ (1\leq a,b\leq 5) a,b  (1≤a,b≤5),表示每盏灯的参数.

思路

显然所有灯开始循环切换状态后所有灯有公共周期,且该公共周期即所有等差数列的公差的 l c m \mathrm{lcm} lcm,再加上最晚进入循环切换状态的灯的 b b b值作为预周期,则只需模拟预周期和第一个周期灯的变化情况即可.

l c m ( 1 , 2 , 3 , 4 , 5 ) = 120 \mathrm{lcm}(1,2,3,4,5)=120 lcm(1,2,3,4,5)=120,再加上最长的预周期 5 5 5,故只需模拟前 125 125 125个时刻.

代码

const int MAXN = 125;
int cnt[MAXN];  // 每个时刻打开的灯的数量

void solve() {
  int n; cin >> n;
  string s; cin >> s;
  for (int i = 0; i < n; i++) {
    int a, b; cin >> a >> b;
    int c = s[i] - '0';
    for (int j = 0; j < MAXN; j++) {  // 枚举时刻
      cnt[j] += c;
      if (j == b) {  // 进入循环切换状态
        c ^= 1;
        b += a;
      }
    }
  }
  cout << *max_element(cnt, cnt + MAXN);
}

int main() {
  solve();
}

---

---

1220B. Multiplication Table

原题指路:https://codeforces.com/problemset/problem/1220/B

题意 ( 2   s ) (2\ \mathrm{s}) (2 s)

给定一个 n × n    ( 3 ≤ n ≤ 1000 ) n\times n\ \ (3\leq n\leq 1000) n×n  (3≤n≤1000)的乘法表 M M M,其元素 M i j = a i a j    ( 1 ≤ M i j ≤ 1 e 9 ) M_{ij}=a_ia_j\ \ (1\leq M_{ij}\leq 1\mathrm{e}9) Mij​=ai​aj​  (1≤Mij​≤1e9),其中 a 1 , ⋯   , a n    ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1​,⋯,an​  (1≤ai​≤1e9)是一个正整数序列.现给定删去对角线元素后的乘法表 M M M,求原序列 a 1 , ⋯   , a n a_1,\cdots,a_n a1​,⋯,an​.

思路

用 ( x y ) ⋅ ( x z ) y z = x 2 \dfrac{(xy)\cdot (xz)}{yz}=x^2 yz(xy)⋅(xz)​=x2计算即可.

代码

const int MAXN = 1005;
int a[MAXN][MAXN];

void solve() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cin >> a[i][j];

  for (int i = 1; i <= n; i++) {
    int j = i % n + 1, k = j % n + 1;
    cout << (int)sqrt((ll)a[i][j] * a[i][k] / a[j][k]) << ' ';
  }
}

int main() {
  solve();
}

---

---