hdu5391威尔逊定理

威尔逊定理

在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。即：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )，但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

hdu5391用到了这一数论定理。

Zball in Tina Town

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

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
0

Source

BestCoder Round #51 (div.2)

题解：

这题就是求 (n−1)!mod n

如果 $n$ 为合数，显然答案为0.

如果 $n$ 为素数，那么由威尔逊定理可得答案为 $n - 1$

注意有个trick为 $n$ = 4

代码：

#include<iostream>
#include<cmath>
#define ll long long 

using namespace std;

int t;
int n,ans;

bool Isprime(int m)
{
    int i,isqrt=(int)sqrt(m);
    bool pd=true;
    if(m==2)pd=true;
    else if(m%2==0)pd=false;
    else 
    for(i=3;i<=isqrt;i+=2){
        if(m%i==0){
            pd=false;
            break;
        }
    }
    return pd;
}

int main()
{
    cin>>t;
    while(t--){
        cin>>n;
        if(n==4)ans=2;
        else if(Isprime(n))ans=n-1;
        else ans=0;
        cout<<ans<<endl;
    }
    return 0;
}

开始一直超时，问题出在判断素数上。

一定要注意素数判定问题。

hdu5391Wilson定理

威尔逊定理

Zball in Tina Town

相关推荐