【Python数学练习1】

一、题目

中文描述：
给出正整数N，输出满足条件的数对(a,b)的个数，满足gcd(a,b)=b, a,b <= n
数学描述：

二、解法

解法1：

对应Python代码：

def num_fact(n):
    num = 0
    for i in range(1, n + 1):
        if n % i == 0:
            num += 1
    return num


# print(num_fact(55))

def Sol1(n):
    ans = 0
    for i in range(1, n + 1):
        ans += num_fact(i)
    return ans


print(Sol1(2))
print(Sol1(3))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出：

输出解释：
输入2，满足条件的(a,b)对为(1,1) (2,1) (2,2)，有3对，故输出3
输入3，满足条件的(a,b)对为(1,1) (2,1) (2,2) (3,1) (3,3)，有5对，故输出5

解法时间复杂度：
对于1到N之间的每个整数i，遍历地寻找i的因子个数，每次耗时为O(N)，故总体时间复杂度为O(N^2)。

解法2：

对应Python代码：
由于要用到向下取整函数floor，我们需要导入Python内建的math数学运算库。

import math
def Sol2(n):
    ans = 0
    for i in range(1, n + 1):
        ans += math.floor(n / i)
    return ans


print(Sol2(2))
print(Sol2(3))

1
2
3
4
5
6
7
8
9
10
11

输出：
解法时间复杂度：
该解法只遍历了一次1到N，故时间复杂度为O(N)，且没有额外的空间复杂度。