GESP二级 - 姐妹数对：找出1到n之间有多少对姐妹数

GESP二级 - 姐妹数对

问题描述:

给定两个不同的正整数x，y，若x+y能被3除尽或能被7除尽，则称x，y为姐妹数对。例如：

• 2, 4；2, 5；为姐妹数对。
• 3, 14； 不是姐妹数对。

那么，对给出的一个整数n(1≤n≤100)， 1,2，…，n之间有多少个姐妹数对。

输入描述:

一个整数n

输出描述:

一个整数，即1～n之间姐妹数对的个数。

用例输入 1:

6

用例输出 1:

8

思路:

根据题目描述，姐妹数对是两个不同的正整数x和y，满足x+y能被3除尽或能被7除尽。那么我们可以遍历1到n之间的每个数，判断它和1到n之间的其他数的和是否能被3或7整除，如果能则计数加1。

具体实现步骤:

1. 读取输入的整数n。
2. 定义一个计数器count，用于记录姐妹数对的个数。
3. 使用两层循环，外层循环遍历1到n之间的每个数i，内层循环遍历1到n之间的每个数j。
4. 判断i+j是否能被3或7整除，如果能则计数器count加1。
5. 循环结束后，输出计数器count的值作为结果。

代码实现 (Python):

n = int(input())
count = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if (i+j) % 3 == 0 or (i+j) % 7 == 0:
            count += 1
print(count)

复杂度分析:

• 该算法使用了两层循环，时间复杂度为O(n^2)，空间复杂度为O(1)。
• 对于输入范围在100以内的n，算法的运行时间是可以接受的。