#2240. 徐老师的矩形

徐老师的矩形

题目描述

徐老师最近做了一道题——《正方形》,这是一道经典的深度优先搜索优化题,很多同学的一生之敌

这道题是这样的,给出 nn 个木棍,要求用所有木棍在不切割的情况下拼成一个正方形,问能否拼出

这题的复杂度很高,优化要求很高,很难

但是很多同学包括徐老师一直有个疑问——木棍怎么就不能切割了?

于是徐老师改编了一道更简单的题目让大家开心开心

徐老师有一个长度为 nn 的木棍,你可以随便切割!

现在要求把这根木棍切割成四条边,组成一个矩形(四条边,相对的两条边相等),并且木棍不能有剩余

而徐老师只有一个要求:组成的矩形面积在 [L,R][L,R] 内(包含 L,RL,R

现在徐老师想知道,这个矩形的短边和长边分别是多长?

P.S. 矩形的短边和长边是可以相等的,此时为正方形(四边相等)

输入格式

输入第一行包含三个正整数 n,L,Rn,L,R

输出格式

输出两个整数,中间用空格隔开,表示能组成的矩形的短边和长边长度,短边在前,长边在后

如果存在多组方案,请输出短边最小的方案,若无解则输出 No answer!

数据范围

对于所有数据保证 1n,L,R10161 \leq n,L,R \leq 10^{16}nn 一定为偶数

每部分数据包含的特殊性质如下

数据点编号 特殊性质
11 L=1,R=1016L=1,R=10^{16}
232 \sim 3 n/2n/2 是质数
464 \sim 6 L=RL=R
7107 \sim 10

样例输入1

20 20 30

样例输出1

3 7

样例解释1

方案有五种:3 77 35 54 66 4,取短边最小的方案 3 7

样例输入2

20 24 26

样例输出2

4 6

样例输入3

10 22 23

样例输出3

No answer!