CF1085B.Div Times Mod

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Vasya likes to solve equations. Today he wants to solve (x div k)⋅(x mod k)=n(x~\mathrm{div}~k) \cdot (x \bmod k) = n, where div\mathrm{div} and mod\mathrm{mod} stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, kk and nn are positive integer parameters, and xx is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible xx. Can you help him?

瓦西里喜欢解方程。今天他想解方程 (x div k)⋅(x mod k)=n(x~\mathrm{div}~k) \cdot (x \bmod k) = n,其中 div\mathrm{div} 和 mod\mathrm{mod} 分别表示整数除法和取模运算(具体定义参见下方“注意”部分)。在此方程中,kk 和 nn 是给定的正整数参数,xx 是待求的正整数未知数。若存在多个解,瓦西里希望找到最小的 xx。你能帮他吗?

输入格式

The first line contains two integers nn and kk (1≤n≤1061 \leq n \leq 10^6, 2≤k≤10002 \leq k \leq 1000).

第一行包含两个整数 nn 和 kk(1≤n≤1061 \leq n \leq 10^6,2≤k≤10002 \leq k \leq 1000)。

输出格式

Print a single integer xx — the smallest positive integer solution to (x div k)⋅(x mod k)=n(x~\mathrm{div}~k) \cdot (x \bmod k) = n. It is guaranteed that this equation has at least one positive integer solution.

输出一个整数 xx —— 方程 (x div k)⋅(x mod k)=n(x~\mathrm{div}~k) \cdot (x \bmod k) = n 的最小正整数解。保证该方程至少存在一个正整数解。

输入输出样例

  • 输入#1

    6 3

    输出#1

    11
  • 输入#2

    1 2

    输出#2

    3
  • 输入#3

    4 6

    输出#3

    10

说明/提示

The result of integer division a div ba~\mathrm{div}~b is equal to the largest integer cc such that b⋅c≤ab \cdot c \leq a. aa modulo bb (shortened a mod ba \bmod b) is the only integer cc such that 0≤c<b0 \leq c \lt b, and a−ca - c is divisible by bb.

In the first sample, 11 div 3=311~\mathrm{div}~3 = 3 and 11 mod 3=211 \bmod 3 = 2. Since 3⋅2=63 \cdot 2 = 6, then x=11x = 11 is a solution to (x div 3)⋅(x mod 3)=6(x~\mathrm{div}~3) \cdot (x \bmod 3) = 6. One can see that 1919 is the only other positive integer solution, hence 1111 is the smallest one.

整数除法 a div ba~\mathrm{div}~b 的结果等于满足 b⋅c≤ab \cdot c \leq a 的最大整数 cc。aa 对 bb 取模(简记为 a mod ba \bmod b)是唯一满足 0≤c<b0 \leq c \lt b 且 a−ca - c 能被 bb 整除的整数 cc。

在第一个样例中,11 div 3=311~\mathrm{div}~3 = 3 且 11 mod 3=211 \bmod 3 = 2。由于 3⋅2=63 \cdot 2 = 6,因此 x=11x = 11 是方程 (x div 3)⋅(x mod 3)=6(x~\mathrm{div}~3) \cdot (x \bmod 3) = 6 的一个解。可以验证 1919 是唯一的另一个正整数解,故 1111 是最小解。

输入解题思路,AI测评打分。不知道怎么写?

首页