【E：Faulty Factorial】(数论，循环节)

本文主要是介绍【E：Faulty Factorial】(数论，循环节)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

**链接**:http://sua2018.contest.codeforces.com/group/J1GbXiu37w/contest/227105

**题意**:在1*2*3*......*n中改变一个数为比它小的数，使得%p等于r.输出任意一个解

2<=n&&n<=1e18

2<=p&&p<1e7

**分析**：n很大，从p入手，考虑循环节。但是真的很暴力

看代码：

#pragma warning(disable:4996)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll p, r;ll qpow(ll a, ll b) {ll res = 1;while (b) {if (b&1) {res = res * a%p;}a = a * a%p;b >>= 1;}return res;
}int main() {scanf("%lld%lld%lld", &n, &p, &r);if (n == p) {if (r == 0) {if (n == 2)printf("-1 -1\n");else printf("2 1\n");}else {int f = 0;printf("%lld %lld\n", p, p - r);}}else if (n >= 2 * p) {if (r == 0) printf("%lld 1\n", p + 1);else printf("-1 -1\n");}else if (n > p) {if (r == 0)printf("%lld 1\n", p + 1);else {int f = 0;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) {printf("%lld %lld\n", p, i);f = 1;break;}}if (!f)printf("-1 -1\n");}}else 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;}}
}

 

这篇关于【E：Faulty Factorial】(数论，循环节)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---