C. Chessboard Billiard

Codeforces

IDCF74C

Time2000ms

Memory256MB

Difficulty—

dfs and similardsugraphsnumber theory

English · Original

Chinese · Translation

Formal · Original

Let's imagine: there is a chess piece _billiard ball_. Its movements resemble the ones of a bishop chess piece. The only difference is that when a billiard ball hits the board's border, it can reflect from it and continue moving. More formally, first one of four diagonal directions is chosen and the billiard ball moves in that direction. When it reaches the square located on the board's edge, the billiard ball reflects from it; it changes the direction of its movement by 90 degrees and continues moving. Specifically, having reached a corner square, the billiard ball is reflected twice and starts to move the opposite way. While it moves, the billiard ball can make an infinite number of reflections. At any square of its trajectory the billiard ball can stop and on that the move is considered completed. <center>![image](https://espresso.codeforces.com/ec0cdb9bd6054853e9d9c88daebd39399a0de32e.png)</center>It is considered that one billiard ball _a_ beats another billiard ball _b_ if _a_ can reach a point where _b_ is located. You are suggested to find the maximal number of billiard balls, that pairwise do not beat each other and that can be positioned on a chessboard _n_ × _m_ in size. ## Input The first line contains two integers _n_ and _m_ (2 ≤ _n_, _m_ ≤ 106). ## Output Print a single number, the maximum possible number of billiard balls that do not pairwise beat each other. Please do not use the _%lld_ specificator to read or write 64-bit numbers in C++. It is preferred to use _cin_ (also you may use the _%I64d_ specificator). [samples]

让我们想象：有一个棋子叫做“台球”。它的移动方式类似于象棋中的象，唯一的区别是，当台球撞到棋盘边界时，它可以发生反射并继续移动。更正式地，首先选择四个对角线方向之一，台球沿该方向移动。当它到达位于棋盘边缘的格子时，台球会从边界反射；它将运动方向改变90度并继续移动。具体来说，当台球到达角落格子时，它会经历两次反射，然后开始沿相反方向移动。在移动过程中，台球可以进行无限次反射。在轨迹上的任意格子，台球都可以停止，此时移动被认为完成。我们认为，一个台球 #cf_span[a] 能“攻击”另一个台球 #cf_span[b]，当且仅当 #cf_span[a] 能到达 #cf_span[b] 所在的位置。你需要找出在大小为 #cf_span[n × m] 的棋盘上，最多能放置多少个台球，使得它们两两之间互不攻击。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n, m ≤ 106]）。请输出一个数字，表示互不攻击的台球的最大可能数量。请不要在 C++ 中使用 _%lld_ 格式符读写 64 位整数。推荐使用 _cin_（你也可以使用 _%I64d_ 格式符）。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n, m ≤ 106]）。 ## Output 请输出一个数字，表示互不攻击的台球的最大可能数量。请不要在 C++ 中使用 _%lld_ 格式符读写 64 位整数。推荐使用 _cin_（你也可以使用 _%I64d_ 格式符）。 [samples]

**Definitions** Let $ n, m \in \mathbb{Z} $ with $ 2 \leq n, m \leq 10^6 $. Let $ G = [n] \times [m] $ be the set of squares of an $ n \times m $ chessboard. Define an equivalence relation $ \sim $ on $ G $: two squares $ (x_1, y_1) \sim (x_2, y_2) $ if a billiard ball starting at $ (x_1, y_1) $ in some diagonal direction can reach $ (x_2, y_2) $ after any number of reflections. **Constraints** - The board has dimensions $ n \times m $. - Movement is diagonal (slope $ \pm 1 $), with reflections off boundaries (angle of incidence = angle of reflection). - A billiard ball’s trajectory is periodic and covers an entire equivalence class under $ \sim $. **Objective** Find the maximum size of a subset $ S \subseteq G $ such that no two distinct elements of $ S $ are in the same equivalence class under $ \sim $. That is, compute the number of equivalence classes of $ \sim $. $$ \boxed{\gcd(n-1, m-1) + 1} $$

Samples

Input #1

3 4

Output #1

Input #2

3 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Chessboard Billiard",
    "description": {
      "content": "Let's imagine: there is a chess piece _billiard ball_. Its movements resemble the ones of a bishop chess piece. The only difference is that when a billiard ball hits the board's border, it can reflect",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF74C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let's imagine: there is a chess piece _billiard ball_. Its movements resemble the ones of a bishop chess piece. The only difference is that when a billiard ball hits the board's border, it can reflect...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "让我们想象：有一个棋子叫做“台球”。它的移动方式类似于象棋中的象，唯一的区别是，当台球撞到棋盘边界时，它可以发生反射并继续移动。\n\n更正式地，首先选择四个对角线方向之一，台球沿该方向移动。当它到达位于棋盘边缘的格子时，台球会从边界反射；它将运动方向改变90度并继续移动。具体来说，当台球到达角落格子时，它会经历两次反射，然后开始沿相反方向移动。在移动过程中，台球可以进行无限次反射。在轨迹上的任意格子...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 2 \\leq n, m \\leq 10^6 $.  \nLet $ G = [n] \\times [m] $ be the set of squares of an $ n \\times m $ chessboard.  \nDefine an equivalence relation $ \\si...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments