CF1108B Divisors of Two Integers

    • 83通过
    • 169提交
  • 题目来源 CodeForces 1108B
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及/提高-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    你得到2个数x与y,可是你忘了。 现在给你n个数字(d1~dn)每个数都是x或y的约数之一,如果一个数字在其中出现了2次,则是x与y的公约数。那么现在叫你求出x与y的可能值(只需要1个解并且保证有解)

    输入:n($2 \le n \le 128$),接下来n个数d1~dn

    输出:x与y的可能解之一

    题目描述

    Recently you have received two positive integer numbers $ x $ and $ y $ . You forgot them, but you remembered a shuffled list containing all divisors of $ x $ (including $ 1 $ and $ x $ ) and all divisors of $ y $ (including $ 1 $ and $ y $ ). If $ d $ is a divisor of both numbers $ x $ and $ y $ at the same time, there are two occurrences of $ d $ in the list.

    For example, if $ x=4 $ and $ y=6 $ then the given list can be any permutation of the list $ [1, 2, 4, 1, 2, 3, 6] $ . Some of the possible lists are: $ [1, 1, 2, 4, 6, 3, 2] $ , $ [4, 6, 1, 1, 2, 3, 2] $ or $ [1, 6, 3, 2, 4, 1, 2] $ .

    Your problem is to restore suitable positive integer numbers $ x $ and $ y $ that would yield the same list of divisors (possibly in different order).

    It is guaranteed that the answer exists, i.e. the given list of divisors corresponds to some positive integers $ x $ and $ y $ .

    输入输出格式

    输入格式:

    The first line contains one integer $ n $ ( $ 2 \le n \le 128 $ ) — the number of divisors of $ x $ and $ y $ .

    The second line of the input contains $ n $ integers $ d_1, d_2, \dots, d_n $ ( $ 1 \le d_i \le 10^4 $ ), where $ d_i $ is either divisor of $ x $ or divisor of $ y $ . If a number is divisor of both numbers $ x $ and $ y $ then there are two copies of this number in the list.

    输出格式:

    Print two positive integer numbers $ x $ and $ y $ — such numbers that merged list of their divisors is the permutation of the given list of integers. It is guaranteed that the answer exists.

    输入输出样例

    输入样例#1: 复制
    10
    10 2 8 1 2 4 1 20 4 5
    
    输出样例#1: 复制
    20 8
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。