TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2929
  • 题目
  • P2929【THOI2014】函数求解
    限制 : 时间限制 : 40000 MS   空间限制 : 565536 KB
    问题描述

    定义正整数域上的函数f(x):N+N+满足:

    满足条件的函数会有很多,例如f(x)=x就是一个解。
    现在给定m,n,求f(n)的最小值。

    输入格式

    由于n可能很大,我们按照质因数分解的形式输入:

    输入第一行包含两个整数m,d。
    接下来d行第i行包含一对整数pi,qi。数据保证pi是质数,pi互补相同,且qi>=1。

    输出格式

    输出一行表示最小的f(n),由于数值比较大,请将输出答案以e为底取对数输出,即ln(f(n)),请保留4位小数。

    样例输入

    2 2
    2 1
    3 2

    样例输出

    2.4849

    提示

    样例解释:
    n=2*32=18,一个可行的最优解为:
      n   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  ...
    f(n)  1   3   2   9   7   6   5  27   4  21  13  18  11  15  14  81  23  12  19  63  ...


    数据范围:
    ┏━━━━━┳━━━━━━━┳━━━━━┳━━━━━━━┓
    ┃ 测试点1  ┃              ┃ 测试点11 ┃              ┃
    ┣━━━━━┫  m<=2,d<=10  ┣━━━━━┫              ┃
    ┃ 测试点2  ┃              ┃ 测试点12 ┃              ┃
    ┣━━━━━╋━━━━━━━╋━━━━━┫  m<=10,d<=50 ┃
    ┃ 测试点3  ┃              ┃ 测试点13 ┃pi<=2000,qi<=5┃
    ┣━━━━━┫  m<=2,d<=10  ┣━━━━━┫              ┃
    ┃ 测试点4  ┃pi<=100,qi<=1 ┃ 测试点14 ┃              ┃
    ┣━━━━━┫              ┣━━━━━┫              ┃
    ┃ 测试点5  ┃              ┃ 测试点15 ┃              ┃
    ┣━━━━━╋━━━━━━━╋━━━━━╋━━━━━━━┫
    ┃ 测试点6  ┃  m<=2,d<=50  ┃ 测试点16 ┃              ┃
    ┣━━━━━┫pi<=1000,qi<=1┣━━━━━┫              ┃
    ┃ 测试点7  ┃              ┃ 测试点17 ┃              ┃
    ┣━━━━━╋━━━━━━━╋━━━━━┫ m<=10,d<=100 ┃
    ┃ 测试点8  ┃              ┃ 测试点18 ┃pi<=2000,qi<=5┃
    ┣━━━━━┫  m<=2,d<=50  ┣━━━━━┫              ┃
    ┃ 测试点9  ┃pi<=1000,qi<=2┃ 测试点19 ┃              ┃
    ┣━━━━━┫              ┣━━━━━┫              ┃
    ┃ 测试点10 ┃              ┃ 测试点20 ┃              ┃
    ┗━━━━━┻━━━━━━━┻━━━━━┻━━━━━━━┛