CERC2017 F: Faulty Factorial 简单数论题

传送门：Faulty Factorial

分析：

分为n==p， n>=2*p, 2*p>n>p , n<p 四种情况讨论

其中n==p使用到了威尔逊定理,且注意， n=p=2，无解

情况不难想，看代码吧

#include <iostream>
using namespace std;
typedef long long LL;
LL n,p,r;
LL qpow(LL a, LL b) {
LL ans = 1;
while (b) {
if (b&1) ans = ans*a%p;
a = a*a%p;
b>>=1;
}
return ans;
}
int main(){
cin >> n >> p >> r;
if (n == p) {
if (r == 0) {
if (n == 2) cout << -1 << " " << -1 << endl;
else cout << 2 << " " << 1 << endl;
return 0;
}
else {
for (LL i=1; i<p; i++)
if (i*(p-1)%p==r) {
cout << p << " " << i << endl;
return 0;
}
cout << -1 << " " << -1 << endl;
return 0;
}
}
if (n>=2*p) {
if (r == 0) cout << p+1 << " " << 1 << endl; else cout << -1 << " " << -1 << endl;
return 0;
}
if (n>p) {
if (r == 0) cout << p+1 << " " << 1 << endl;
else {
LL t = 1;
for (LL i=2; i<=n; i++) if (i!=p) t = t*i%p;
for (LL i=1; i<p; i++) if (t*i%p==r) { cout << p << " " << i << endl; return 0; }
cout << -1 << " " << -1 << endl;
}
return 0;
}
if (n<p) {
if (r == 0) cout << -1 << " " << -1 << endl;
else {
LL t = 1;
for (LL i=2; i<=n; i++) t = t*i%p;
t =
qpow(t,p-2);
for (LL i=2; i<=n; i++) {
LL tmp = r*i%p*t%p;
if (tmp>=1 && tmp<i) { cout << i << " " << tmp << endl; return 0; }
}
cout << -1 << " " << -1 << endl;
}
}
return 0;
}

最后

以上就是要减肥面包最近收集整理的关于CERC2017 F: Faulty Factorial 简单数论题的全部内容，更多相关CERC2017内容请搜索靠谱客的其他文章。