2014
03-02

# Cover the Square

Oh no! The Enterprise is being attacked by a Borg unit cube. We all know that resistance is futile, but that won’t prevent the captain from trying anyway!

The engineers aboard the Enterprise have recently upgraded the size of the ships’s laser beam weapons, such that it can now cut large circular holes into enemy ships. In fact, they can even cut out holes of diameter one, which should get rid of most of the Borg cube in one deadly blow. However, the Borgs are frighteningly persistent, and the captain fears that the remaining undestroyed pieces will cause trouble. Thus, he wants to destroy at least n percent of the cube.

The Borg cube is positioned such that one of its faces is perpendicular to the enterprise’s line of sight, so the problem is approximately equivalent to trying to cover a unit square with circles of diameter one. Under this approximation and assuming that the undestroyed parts simply remain motionless at their original position, how many shots are required to destroy at least n percent of the cube?

The first line of the input will contain m, the number of test cases. m lines will follow, each containing an integer n between 0 and 100 inclusively.

The first line of the input will contain m, the number of test cases. m lines will follow, each containing an integer n between 0 and 100 inclusively.

3
0
50
100

0
1
4

1. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n