TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2376
  • 题目
  • P2376【NOIP无压力模拟赛5】蜘蛛展览
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    话说育母蜘蛛搞了一批小蜘蛛……于是育母蜘蛛要跟小蜘蛛们玩个游戏……育母蜘蛛让小蜘蛛们按照 1 到K 的顺序报数,报完K 后再报 1,每次报K 的小蜘蛛就会受到惩罚,小蜘蛛们在报数之前就 知道谁要受惩罚,于是一些小蜘蛛结成了同盟,小蜘蛛的同 盟很有意思,两只小蜘蛛是同盟当且仅当两只小蜘蛛的最大公约数不为 1。

    现在育母蜘蛛要带一些小蜘蛛去参加展览,育母蜘蛛希望带的 小蜘蛛里任意两只都不是同盟,现在育母蜘蛛想知道它最多能带多少 只小蜘蛛,在个数最多的情况下,育母蜘蛛还想知道所带的小蜘蛛总 的编号和最小是多少。

    输入格式

    第一行一个数 T,表示数据组数
    接下来T 行,每行一个数字N,表示小蜘蛛的数量

    输出格式

    T行,每行两个数,用空格隔开,表示两个问题的答案。

    样例输入

    2
    3
    9

    样例输出

    3 6
    5 18

    提示

    T≤100000,N≤10000000


    来源  hzoi