Fansblog 威尔逊定理

题目描述： Farmer John keeps a website called ‘FansBlog’ .Everyday , there
are many people visited this blog.One day, he find the visits has
reached P , which is a prime number.He thinks it is a interesting
fact.And he remembers that the visits had reached another prime
number.He try to find out the largest prime number Q ( Q < P ) ,and
get the answer of Q! Module P.But he is too busy to find out the
answer. So he ask you for help. ( Q! is the product of all positive
integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… *
3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 ) 输入： First line
contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P
(1e9≤p≤1e14) 输出： For each testcase, output an integer representing the
factorial of Q modulo P. 样例输入： 1 1000000007 样例输出： 328400734

威尔逊定理：

（p-2）！= 1

求 q！%p
已知（p-2）！%p= 1， p>q
q! * (p-2)（p-3）…(q+1) = ( p-2)!

则 q! *( (p-2)…(q+1) ) %p=1
q!%p = ( (p-2)…(q+1) )的逆元%p

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll pp(ll a,ll b,ll mod)
{a%=mod;b%=mod;ll sum=0;while(b){if(b&1){sum=(sum+a)%mod;}b>>=1;a=a*2%mod;}sum%=mod;return sum;
}//a*b%m
ll ff(ll a,ll b,ll mod)
{ll ans=1;while(b){if(b&1)ans=pp(ans,a,mod);a=pp(a,a,mod);b>>=1;}return ans;
}//a^b%m
bool isPrime_3( ll num )
{//两个较小数另外处理if(num ==2|| num==3 )return 1 ;//不在6的倍数两侧的一定不是质数if(num %6!= 1&&num %6!= 5)return 0 ;ll tmp =sqrt( num);//在6的倍数两侧的也可能不是质数for(ll i= 5;i <=tmp; i+=6 )if(num %i== 0||num %(i+ 2)==0 )return 0 ;//排除所有，剩余的是质数return 1 ;
}//速判素数
int main()
{int t;scanf("%d", &t);while(t--){ll w,p,q,z=1,ny;scanf("%lld", &p);w=p;while(w--){if(isPrime_3(w)){q=w;break;}}for(ll i=q+1;i<=p-2;i++){z=pp(z,i,p);}z%=p;ny=ff(z,p-2,p)%p;///逆元%pprintf("%lld\n",ny);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！