首先咱们先把核心约束掰扯清楚：所有直线必须互不平行（也就是斜率得唯一，包括垂直、水平这种特殊斜率的情况），而且直线只能和正方形边界的整数位置（1~N-1）相交。下面是分步骤的高效实现思路：

1. 先处理特殊斜率（水平/垂直） #

• 垂直直线：只有x = k（k∈1..N-1）这类，所有垂直直线都是互相平行的，所以最多只能选1条。如果需要包含垂直直线，随机挑一个1到N-1之间的整数k就行。
• 水平直线：只有y = k（k∈1..N-1）这类，同理最多选1条。如果需要，随机选一个1到N-1之间的整数k即可。

注意：如果M≥2，你可以同时选一条水平和一条垂直（它们肯定不平行），但绝对不能选多条水平或者多条垂直。

2. 生成非水平非垂直的唯一斜率直线 #

这部分是核心，我们要生成斜率绝对不重复的直线，同时保证每条直线都满足和边界整数位置相交的要求。这里有两种高效的实现方式：

方式一：基于斜率唯一性按需生成 #

因为直线的斜率由两个边界交点的坐标差决定，我们可以这么做：

• 先维护一个集合used_slopes，用来存已经生成的斜率的最简分数形式（比如用元组(分子, 分母)表示，要求分子分母互质，且分母为正，这样能快速判断斜率是否重复）。
• 循环直到生成足够数量的直线（减去已经选的水平/垂直数量）：
  1. 随机选一种边界连接类型：要么连接对边（左-右、上-下），要么连接邻边（左-上、左-下、右-上、右-下）。
  2. 随机生成对应的交点坐标：比如选左边界的(0,a)和右边界的(N,b)，其中a和b都是1到N-1之间的整数。
  3. 计算斜率的最简分数：比如这条直线的斜率是(b - a)/N，先算分子分母的最大公约数gcd，然后把分子分母都除以gcd，保证分母为正（如果分子是负数就保留负号）。
  4. 如果这个最简斜率不在used_slopes里，就把它加入集合，同时记录这条直线的方程（用两点式或者斜截式都可以）。

方式二：预先生成所有唯一斜率直线，再随机抽样 #

如果N不大，预先生成所有符合条件的唯一斜率直线，再用无放回随机抽样选M条，速度会非常快：

• 遍历所有可能的边界交点对（排除水平、垂直的情况），计算每条直线的最简斜率，去重后得到一个唯一直线的列表。
• 直接从这个列表里随机挑M条就行。这种方法适合N较小的场景，预计算成本低，抽样几乎是O(1)的操作。

3. 实用优化技巧 #

• 对于大N的场景，方式一更高效，因为不需要预先生成所有可能的直线，按需生成能避免内存占用过大。
• 用最简分数作为斜率的唯一标识时，哈希集合的查找是O(1)的，判断重复的速度极快。
• 生成前可以先估算总共有多少唯一斜率，确保M不超过这个数量（否则根本无法满足条件）。比如总唯一斜率数 = 1（垂直） + 1（水平） + 所有非水平非垂直的唯一斜率数。

举个小例子：当N=3时，3×3正方形的边界整数位置只有1。可能的非水平非垂直直线包括(0,1)-(3,2)（斜率1/3）、(0,1)-(2,3)（斜率1）、(3,1)-(1,0)（斜率-1/2）等等，每个斜率只保留一条对应的直线。

内容的提问来源于stack exchange，提问作者Mohammad Al-Turkistany