【数论+思维】 GYM101620F Faulty Factorial

http://codeforces.com/gym/101620/attachments

给你n,p,r,(1<=n<=1e18,p是<=1e7的质数，r<p)

n!中任选一个数换成比此数小的数，要求得到的新的乘积%p==r，问是否可以

不可以输出 -1 -1，可以输出 a b，(把a换成b)

分类讨论

1、r==0,如果r==0,

    (1) 当n<=2||n<p 1-n中没有p，那么改后的n!%p 一定不为0,  输出 -1 -1

    (2) 否则 将除p之外的数改掉就行

2、 r！=0

    （1）n>=2*p   因为1*2*……p*（p+1）*……2p*……*n  %p ==0(不管怎么改，都不可能使余数不为0)  输出 -1 -1

    （2）n>=p&&n<2*p   因为1*2*……p*……*n  %p ==0（只要把p改了，for循环，看1-p-1，哪个符合，输出即可）

    （3）n<p    寻找a,b 满足 n!*（b/a）%p==r   --->  n!*b%p=r*a --->   b=r*a*inv[n!]%p   遍历a，看b符不符合b<a，符合输出即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll quickpow(ll x,int n,int mod)
{
ll res=1;
while(n>0)
{
if(n&1) res=1LL*res*x%mod;
x=1LL*x*x%mod;
n>>=1;
}
return res;
}
int main()
{
ll n;
int p,r;
int flag=0;
scanf("%lld%d%d",&n,&p,&r);
if(r==0)
{
if(n<=2||n<p)
printf("-1 -1n");
else
printf("%d 1n",2+(p==2));
return 0;
}
else
{
if(n>=2*p) printf("-1 -1n");
else if(n>=p&&n<2*p)
{
ll ans=1;
for(int i=1;i<=n;i++)
{
if(i!=p) ans=ans*i%p;
}
for(int i=1;i<p;i++)
{
if(ans*i%p==r)
{
printf("%d %dn",p,i);
return 0;
}
}
printf("-1 -1n");
}
else
{
ll ans=1;
for(int i=1;i<=n;i++)
{
ans=ans*i%p;
}
ll inv=quickpow(ans,p-2,p);
for(int i=1;i<=n;i++)
{
ll b=1LL*r*i%p*inv%p;
if(b<i)
{
printf("%d %lldn",i,b);
return 0;
}
}
printf("-1 -1n");
}
return 0;
}
}

最后

以上就是缓慢蜜粉为你收集整理的【数论+思维】 GYM101620F Faulty Factorial的全部内容，希望文章能够帮你解决【数论+思维】 GYM101620F Faulty Factorial所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。