CF1184A1.Heidi Learns Hashing (Easy)

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Melody Pond was stolen from her parents as a newborn baby by Madame Kovarian, to become a weapon of the Silence in their crusade against the Doctor. Madame Kovarian changed Melody's name to River Song, giving her a new identity that allowed her to kill the Eleventh Doctor.

Heidi figured out that Madame Kovarian uses a very complicated hashing function in order to change the names of the babies she steals. In order to prevent this from happening to future Doctors, Heidi decided to prepare herself by learning some basic hashing techniques.

The first hashing function she designed is as follows.

Given two positive integers (x,y)(x, y) she defines H(x,y):=x2+2xy+x+1H(x,y):=x^2+2xy+x+1.

Now, Heidi wonders if the function is reversible. That is, given a positive integer rr, can you find a pair (x,y)(x, y) (of positive integers) such that H(x,y)=rH(x, y) = r?

If multiple such pairs exist, output the one with smallest possible xx. If there is no such pair, output "NO".

梅洛迪·庞德在婴儿时期就被科瓦里安夫人从父母身边掳走,成为“寂静”组织对抗博士的武器。科瓦里安夫人为梅洛迪改名为“河 Song”(River Song),赋予她一个新身份,使其得以刺杀第十一任博士。

海蒂发现,科瓦里安夫人使用了一种极为复杂的哈希函数来更改她所掳走婴儿的名字。为了防止未来博士们遭遇同样的命运,海蒂决定提前学习一些基础的哈希技术以作准备。

她设计的第一个哈希函数定义如下:

给定两个正整数 (x,y)(x, y),定义 H(x,y):=x2+2xy+x+1H(x,y):=x^2+2xy+x+1。

现在,海蒂想知道该函数是否可逆:即,对于给定的正整数 rr,能否找到一对正整数 (x,y)(x, y),使得 H(x,y)=rH(x, y) = r?

若存在多对满足条件的 (x,y)(x, y),请输出其中 xx 值最小的一对;若不存在这样的数对,则输出 "NO"。

输入格式

The first and only line contains an integer rr (1≤r≤10121 \le r \le 10^{12}).

第一行且唯一一行包含一个整数 rr(1≤r≤10121 \le r \le 10^{12})。

输出格式

Output integers x,yx, y such that H(x,y)=rH(x,y) = r and xx is smallest possible, or "NO" if no such pair exists.

输出整数 x,yx, y,使得 H(x,y)=rH(x,y) = r,且 xx 尽可能小;若不存在这样的数对,则输出 "NO"。

输入输出样例

  • 输入#1

    19

    输出#1

    1 8
  • 输入#2

    16

    输出#2

    NO

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

首页