[常州市赛 2023] 红绿灯

Luogu

IDLGB4221

Time1000ms

Memory512MB

DifficultyP4

2023数论江苏最大公约数 gcd中国剩余定理 CRT科创活动小学活动

小 X 家门前有两个红绿灯，小 X 做完了数学作业，闲着无聊便在窗边观察。他发现这两个红绿灯亮红灯和亮绿灯的时间是相等的，第一个红绿灯亮 $p$ 秒绿灯，再亮 $p$ 秒红灯……，第二个红绿灯亮 $q$ 秒绿灯，再亮 $q$ 秒红灯……，如此循环往复。现在恰好两个红绿灯都从红灯变成了绿灯，小 X 想要知道未来的 $2\times p\times q$ 秒内，有多少秒满足两个红绿灯都亮绿灯。 ## Input 第一行 $2$ 个正整数 $p,q$，含义见题面。 ## Output 输出一行一个整数表示在未来的 $2\times p\times q$ 秒内，有多少秒满足两个红绿灯都亮绿灯。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/678>。数据为民间数据。 ## Note ### 样例 $\textbf 1$ 解释在未来的 $12$ 秒内，第一个红绿灯在第 $1,2,5,6,9,10$ 秒亮绿灯。第二个红绿灯在第 $1,2,3,7,8,9$ 秒亮绿灯。在第 $1,2,9$ 秒时，同时亮绿灯，一共 $3$ 秒。 ### 数据范围本题共有 $12$ 个测试点。 |测试点编号|$p,q$|特殊性质| |:-:|:-:|:-:| |$1\sim3$|$1\le p,q\le 1000$|无| |$4\sim5$|$1=p\le q\le 10^9$|无| |$6\sim9$|$1\le p,q\le10^9$|$p\perp q$| |$10\sim12$|$1\le p,q\le 10^9$|无|

Samples

Input #1

2 3

Output #1

Input #2

18 66

Output #2

Input #3

1 255

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[常州市赛 2023] 红绿灯",
    "description": {
      "content": "小 X 家门前有两个红绿灯，小 X 做完了数学作业，闲着无聊便在窗边观察。他发现这两个红绿灯亮红灯和亮绿灯的时间是相等的，第一个红绿灯亮 $p$ 秒绿灯，再亮 $p$ 秒红灯……，第二个红绿灯亮 $q$ 秒绿灯，再亮 $q$ 秒红灯……，如此循环往复。 现在恰好两个红绿灯都从红灯变成了绿灯，小 X 想要知道未来的 $2\\times p\\times q$ 秒内，有多少秒满足两个红绿灯都亮绿灯。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4221"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 X 家门前有两个红绿灯，小 X 做完了数学作业，闲着无聊便在窗边观察。他发现这两个红绿灯亮红灯和亮绿灯的时间是相等的，第一个红绿灯亮 $p$ 秒绿灯，再亮 $p$ 秒红灯……，第二个红绿灯亮 $q$ 秒绿灯，再亮 $q$ 秒红灯……，如此循环往复。\n\n现在恰好两个红绿灯都从红灯变成了绿灯，小 X 想要知道未来的 $2\\times p\\times q$ 秒内，有多少秒满足两个红绿灯都亮绿灯。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments