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)不合题意,其余均满足条件。

    		<p>&nbsp;</p>
    
    		<table style="width:568px">
    			<tbody>
    				<tr>
    					<td style="width:284px">
    					<p>样例说明2</p>
    					</td>
    				</tr>
    				<tr>
    					<td style="width:284px">
    					<p>在满足1&lt;=a&lt;=b&lt;=7的条件下,共有28对;其中(2,2),(2,4),(2,6),(3,3),(3,6),</p>
    
    					<p>(4,4),(4,6),(5,5),(6,6)不合题意.</p>
    					</td>
    				</tr>
    			</tbody>
    		</table>
    		</td>
    	</tr>
    </tbody>
    

    来源  LYM