统计桌面上的不同数字

给你一个正整数 n ，开始时，它放在桌面上。在 $10^9$ 天内，每天都要执行下述步骤：

对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
然后，将这些数字放在桌面上。
返回在 $10^9$ 天之后，出现在桌面上的 不同 整数的数目。

注意：

• 一旦数字放在桌面上，则会一直保留直到结束。
• % 表示取余运算。例如，14 % 3 等于 2 。

Own Solution:

class Solution(object):
    def distinctIntegers(self, n):
        """
        :type n: int
        :rtype: int
        """
        table = [n]
        if n == 1:
            return 1
        for i in range(2,n):
            if i-1 not in table:
                table.append(n-1)
        return len(table)

要注意的点是特殊判断的1。看了提示才做出来的^^。

官方解法1：模拟

用数组记录桌面上已经出现的正整数，num[n] = 1表示桌面上只出现正整数n。每天都对桌面上已经出现的数字进行遍历，判断符合条件放到桌面上既可（令数组中该标号的数字的值为1）。最后统计num中值为1的元素数目即可。（用sum就可以了）

class Solution(object):
    def distinctIntegers(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = [0] * (n+1)
        nums[n] = 1
        for _ in range(0,n):
            for x in range(1,n+1):
                if nums[x] == 0:
                    continue
                for i in range(1,n+1):
                    if x % i == 1:
                        nums[i] = 1
        return sum(nums)

但是时间复杂度到了O($n^3$)，所以一开始想到这样判断但怕会超时就直接放弃了这种解法。

官方解法2：数学

根据题目的特殊性，10的9次方是很大的操作次数，所以可以默认一定可以将所有小于n的正整数（除了1）放到桌面上。所以除去1的特解，答案就是n-1。

class Solution:
    def distinctIntegers(self, n):
        return 1 if n == 1 else n - 1

评论区：搞笑题。（赞成

但也算是给了一个可以走捷径的思路吧，所以记下。