TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3801
  • 题目
  • P3801分解质因数
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    问题描述

    记Pi表示正整数i的质因数集合。

    已知正整数n,求满足下列条件的有序正整数对(a,b)的数目:

    (1)1<=a<=b<=n
    (2)t为a,b的最大公约数,Pt是Pn的子集

    输入格式

    一个正整数n.

    输出格式

    一个正整数,表示合题意的有序正整数对的数目.

    样例输入 1

    6

    样例输出 1

    20

    样例输入 2

    7

    样例输出 2

    19

    提示

    [数据范围]

    50%的数据1<=n<=2000;

    100%的数据1<=n<=1000000.

     

    样例说明1

    在满足1<=a<=b<=6的条件下,共有21对;除开(5,5)不合题意,其余均满足条件。

     

    样例说明2

    在满足1<=a<=b<=7的条件下,共有28对;其中(2,2),(2,4),(2,6),(3,3),(3,6),

    (4,4),(4,6),(5,5),(6,6)不合题意.


    来源  LYM