hdu5391 Zball in Tina Town

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  time as large as its original size. On the second day,it will become times as large as the size on the first day. On the n-th day,it will become  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.

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

The following  lines, each line contains an integer , according to the description.

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

这题求的是(n-1)!%n,根据打表发现，当n是4的时候输出2，其他如果是素数的话就输出n-1，否则输出0.用了线性素数筛法，时间少了很多。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define maxn 400000
int prime[maxn+10],vis[maxn+10],tot;
void init()
{
    int i,j;
    tot=0;
    for(i=2;i<=maxn;i++){
        if(!vis[i]){
            tot++;prime[tot]=i;
        }
        for(j=1;j<=tot &&prime[j]*i<=maxn;j++){
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}



int main()
{
    int n,m,i,j,num,T,flag;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        if(n==4){
            printf("2
");continue;
        }
        if(n<=maxn){
            if(!vis[n]){
                printf("%d
",n-1);
            }
            else printf("0
");
            continue;
        }
        flag=1;
        for(i=1;i<=tot && prime[i]*prime[i]<=n;i++){
            if(n%prime[i]==0){
                flag=0;break;
            }
        }
        if(flag)printf("%d
",n-1);
        else printf("0
");
    }
    return 0;
}