Problem8355--最大公约数

8355: 最大公约数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

给一个正整数 $n$。
你的任务就是找出所有可能的最大公约数的值，并统计正整数 $1 \sim n$ 中与 $n$ 的最大公约数是这个值的数有多少个。

Input

输入包括一行一个正整数 $n\ (1 \leq n \leq 4,000,000,000,000)$。

Output

输出若干行，每行两个正整数 $m, x$，表示正整数 $1\sim n$ 中，有 $x$ 个数和n的最大公约数为 $m$。
对于每行的 $m_i, x_i$，你需要保证 $x_i>0$，且 $m_i$ 按升序顺序输出。

Sample 1 Input 

30

Sample 1 Output 

1 8
2 8
3 4
5 2
6 4
10 2
15 1
30 1
在 $1 \sim 30$ 中与 $30$ 的公约数分布如下：
公约数为 $1$ 的有，$1,7,11,13,17,19,23,29$。合计 $9$ 个。
公约数为 $2$ 的有，$2,4,8,14,16,22,26,28$。合计 $8$ 个。
公约数为 $3$ 的有，$3,9,21,27$。合计 $3$ 个。
公约数为 $5$ 的有，$5,25$。合计 $2$ 个。
公约数为 $6$ 的有，$6,12,18,24$。合计 $4$ 个。
公约数为 $10$ 的有，$10,20$。合计 $2$ 个。
公约数为 $15$ 的有，$15$。合计 $1$ 个。
公约数为 $30$ 的有，$30$。合计 $1$ 个。

Sample 2 Input 

1000000007

Sample 2 Output 

1 1000000006
1000000007 1

Sample 3 Input 

64

Sample 3 Output 

1 32
2 16
4 8
8 4
16 2
32 1
64 1

Source/Category

 
Submit