Solutions CS101

Appearance

E01218: THE DRUNK JAILER ​

math, implementation, http://cs101.openjudge.cn/practice/01218/

A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner in it, and each cell is locked. One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the hall locking every other cell (cells 2, 4, 6, ?). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He repeats this for n rounds, takes a final drink, and passes out. Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape. Given the number of cells, determine how many prisoners escape jail.

输入

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.

输出

For each line, you must print out the number of prisoners that escape when the prison has n cells.

样例输入

2
5
100

样例输出

2
10

来源

Greater New York 2002

题意是给定n个牢房时逃生的囚犯数量。

数学思维：关键在于理解每个开关（即每个牢房的锁）会被拨动的次数是其编号的因子个数。由于初始状态是所有牢房都是锁定的，每次拨动会改变锁的状态（锁定变为解锁，或解锁变为锁定）。因此，一个牢房最终是解锁的当且仅当其被拨动了奇数次，即其编号的因子个数为奇数。而只有完全平方数的因子个数是奇数，因为因子是成对出现的，只有完全平方数有一个独自的因子（如 4 的因子是 1, 2, 4，其中 2 是独自的）

因此，对于给定的 n 个牢房，逃生的囚犯数量就是 n 以内的完全平方数的个数，即 int(n ** 0.5)。

python
for i in range(int(input())):
    print(int(int(input())**0.5))

计算机思维：模拟法。通过模拟开关过程来解决（虽然效率较低，但更直观）。

python
for _ in range(int(input())):
    n = int(input())
    cells = [False] * (n + 1)  # False表示锁着，True表示开着

    for round in range(1, n + 1):
        for cell in range(round, n + 1, round):
            cells[cell] = not cells[cell]

    print(sum(cells[1:]))  # 计数开着的牢房