hdu5391 Zball in Tina Town(威尔逊定理)

转载请注明出处： http://www.cnblogs.com/fraud/          ——by fraud

Zball in Tina Town

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 219    Accepted Submission(s): 144

Problem Description

Tina Town is a friendly place. People there care about each other.

Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day, it becomes 1 time as large as its original size. On the second day,it will become 2 times as large as the size on the first day. On the n-th day,it will become n times as large as the size on the (n-1)-th day. Tina want to know its size on the (n-1)-th day modulo n.

Input

The first line of input contains an integer T, representing the number of cases.

The following T lines, each line contains an integer n, according to the description.
T≤105,2≤n≤109

Output

For each test case, output an integer representing the answer.

Sample Input

2

3

10

Sample Output

2

题意：要求(n-1)! mod n
根据威尔逊定理，n为素数的时候(n-1)! mod n = -1 = n - 1，这是个充要条件

在n不是素数的时候，可以发现，只有4不为0，其余的时候都为0

 /**
  * code generated by JHelper
  * More info: https://github.com/AlexeyDmitriev/JHelper
  * @author xyiyy @https://github.com/xyiyy
  */

 #include <iostream>
 #include <fstream>

 //#####################
 //Author:fraud
 //Blog: http://www.cnblogs.com/fraud/
 //#####################
 //#pragma comment(linker, "/STACK:102400000,102400000")
 #include <iostream>
 #include <sstream>
 #include <ios>
 #include <iomanip>
 #include <functional>
 #include <algorithm>
 #include <vector>
 #include <string>
 #include <list>
 #include <queue>
 #include <deque>
 #include <stack>
 #include <set>
 #include <map>
 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <climits>
 #include <cctype>

 using namespace std;

 //
 // Created by xyiyy on 2015/8/7.
 //

 #ifndef ICPC_SCANNER_HPP
 #define ICPC_SCANNER_HPP

 #endif //ICPC_SCANNER_HPP

 class hdu5391 {
 public:
     void solve(std::istream &in, std::ostream &out) {
         int t;
         in >> t;
         while (t--) {
             int n;
             in >> n;
             if (check(n))out << n -  << endl;
             else if (n == )out <<  << endl;
             else out <<  << endl;
         }
     }

     bool check(int x) {
         for (int i = ; i * i <= x; i++) {
             if (x % i == ) {
                 return ;
             }
         }
         return ;
     }
 };

 int main() {
     std::ios::sync_with_stdio(false);
     std::cin.tie();
     hdu5391 solver;
     std::istream &in(std::cin);
     std::ostream &out(std::cout);
     solver.solve(in, out);
     return ;
 }