Time Limit: 1000ms Memory Limit: 512MB Description Please calculate ⌊ cos 2 ( ( n − 1 ) ! + 1 n π ) ⌋ ⌊\cos^2{(\frac{(n-1)!+1}{n}}π)⌋ ⌊cos2(n(n−1)!+1π)⌋ Input First line contains an integer T (1 ≤ T ≤ 1 0 3 10^3 103) represents the number of test cases. For each test case: The first line contains an integer n (2 ≤ n ≤ 1 0 9 10^9 109) represents the number of grids the king needed. Output For each test case, output a line contains an integer represents the answer. Sample Input 3 3 4 5 Output 1 0 1 Hint ⌊x⌋ means the maximum integer not greater than x. n! means 1 ∗ 2 ∗ … ∗ (n − 1) ∗ n.
题目大意： 输入一个整数n，求出公式的结果。 分析： 就是一道简单的数论题，用的是威尔逊定理。 首先，公式是 cos 2 \cos^2 cos2向下取整，那么结果只有两种可能，1或0(自己先思考一下为什么)。 我们都知道cos的范围是[-1, 1]，那么 cos 2 \cos^2 cos2的范围就是[0, 1]，向下取整之后，除了1以外，其他结果都是0。 很显然，得1的概率比得0的概率低很多的，所以我们可以先考虑一下什么时候表达式的值会得1。简单反推一下，有以下结果： ⌊ cos 2 ( ( n − 1 ) ! + 1 n π ) ⌋ = 1 ⇒ cos ( ( n − 1 ) ! + 1 n π ) = 1 或 − 1 ⇒ ( ( n − 1 ) ! + 1 ) % n = 0 ⇒ ( n − 1 ) ! % n = − 1 ⌊\cos^2{(\frac{(n-1)!+1}{n}}π)⌋ =1\\ \Rightarrow \cos{(\frac{(n-1)!+1}{n}}π) = 1或-1 \\ \Rightarrow ((n-1)!+1)\ \%\ n = 0 \\ \Rightarrow (n-1)!\ \%\ n = -1 ⌊cos2(n(n−1)!+1π)⌋=1⇒cos(n(n−1)!+1π)=1或−1⇒((n−1)!+1) % n=0⇒(n−1)! % n=−1 推到这里，想来该会的人也都会了，那就是威尔逊定理：最后的等式成立时，当且仅当n为质数。 PS： 这里说一些题外话。当时比赛的时候，我们还真就不知道这个定理。但这道题也不是不能做。 首先， 1 0 9 10^9 109的阶乘暴力是一定超时的，但cos函数又一定是有规律的，何况平方向下取整只有1和0，且1的概率很小，也是没问题的。那么这道题就一定可以找出一个规律来。 所以，我们当时就写了一个暴力的函数，然后输出了 n ∈ [ 2 , 100 ] n \in[2, 100] n∈[2,100]中所有结果为1的值n。输出结果为：2, 3, 5, 7, 11, 13, 17, ……很明显，n是质数！当时我和队友小明{豁然开朗.jpg} 当然，这只是一种取巧的方法，还是推荐要多学知识的。不过AC才是真理，谁能保证自己每个知识点都会？思路才是王道，它才能帮你克服一切难关解决问题。 代码如下：
#include <iostream> using namespace std; int t, n; //判断num是否为素数 bool check(int num) { for(int i = 2; i * i <= num; i++) if(num % i == 0) return false; return true; } int main() { scanf("%d", &t); while(t--) { scanf("%d", &n); printf("%d\n", check(n) ? 1 : 0); } return 0; }