hdu 5391 Zball in Tina Town

点击此处即可传送 hdu 5391
唉，我以为带7的基本上都是素数，所以一直拿1007算，结果。。。。唉，一把辛酸泪啊，算了，不说了，上正事：

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 111 time as large as its original size. On the second day,it will become 222 times as large as the size on the first day. On the n-th day,it will become nnn 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 TTT, representing the number of cases.

The following TTT lines, each line contains an integer nnn, according to the description. T≤105,2≤n≤109 T \leq {10}^{5},2 \leq n \leq {10}^{9} T≤10
​5
​​,2≤n≤10
​9
​​


Output


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


Sample Input

2
3
10


Sample Output

2
0

题目大意：就是算（n-1）!%n，
解题思路：唉，就是当时素数的时候，取n-1，是合数的时候是0，4除外，当n==4的时候取2；

注意 1007不是素数

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = 1e5;
bool data[maxn];
LL fac[10000];
int cnt = 0;
void isprime()
{
    memset(data,1,sizeof(data));
    for(LL i=2; i<maxn; i++)
    {
        if(data[i])
        {
            fac[cnt++]=i;
            for(LL j=i*i; j<maxn; j+=i)
                data[j] = 0;
        }
    }
}
int main()
{
    int t,m;
    //cnt = 0;
    isprime();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&m);
        if(m == 4)
            cout<<2<<endl;
        else
        {
            int flag =0;
            for(int i=0; i<cnt; i++)
            {
                //cout<<fac[i]<<" ";
                if(fac[i]*fac[i] > m)
                    break;
                if(m%fac[i]==0)
                {
                    flag=1;
                    //cout<<flag<<endl;
                    break;
                }
            }
            if(flag == 1)
                puts("0");
            else
                printf("%d\n",m-1);
        }
    }
    return 0;
}