ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210237 | #3789. 我可能是C题 | _Alexande_ | 100 | 4305ms | 266604kb | C++11 | 2.5kb | 2024-08-06 09:37:25 | 2024-08-06 13:01:43 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define lep( i, l, r ) for ( int i = ( l ); i <= ( r ); ++ i )
#define rep( i, r, l ) for ( int i = ( r ); i >= ( l ); -- i )
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
char _c; bool _f; template < class type > inline void read ( type &x ) {
_f = 0, x = 0;
while ( _c = getchar (), !isdigit ( _c ) ) if ( _c == '-' ) _f = 1;
while ( isdigit ( _c ) ) x = x * 10 + _c - '0', _c = getchar (); if ( _f ) { x = -x; }
}
template < class type > inline void chkmin ( type &x, type y ) { x = ( x <= y ? x : y ); }
template < class type > inline void chkmax ( type &x, type y ) { x = ( x >= y ? x : y ); }
const int N = 2e7 + 5;
int n, mod, r;
int pre[N], suf[N];
int fast_pow ( int a, int b ) {
int res = 1;
while ( b ) {
if ( b & 1 ) {
res = res * a;
res %= mod;
}
b >>= 1;
a = a * a;
a %= mod;
}
return res;
}
int exgcd ( int a, int b, int &x, int &y ) {
if ( !b ) {
x = 1, y = 0;
return a;
}
int d = exgcd ( b, a % b, y, x );
y -= a / b * x;
return d;
}
int inv[N];
void Solve () {
ios :: sync_with_stdio ( false );
cin.tie ( 0 ), cout.tie ( 0 );
cin >> n >> mod >> r;
pre[0] = 1;
for ( int i = 1; i <= min ( n, mod ); i ++ ) {
pre[i] = pre[i - 1] * i;
pre[i] %= mod;
}
suf[min ( 2 * min ( n, mod ), n ) + 1] = 1;
for ( int i = min ( 2 * min ( n, mod ), n ); i >= 1; i -- ) {
suf[i] = suf[i + 1] * i;
suf[i] %= mod;
}
inv[1] = 1;
for ( int i = 2; i <= mod; i ++ ) {
inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
}
for ( int i = 1; i <= min ( 2 * min ( n, mod ), n ); i ++ ) {
if ( pre[i - 1] * suf[i + 1] % mod == 0 ) {
if ( !r && i > 1 ) {
cout << i - 1 << " " << i;
return ;
}
continue;
}
// for ( int j = 1; j < i; j ++ ) {
// if ( pre[i - 1] * suf[i + 1] % mod * j % mod == r ) {
// cout << j << " " << i << '\n';
// return ;
// }
// }
int tmp = inv[pre[i - 1] * suf[i + 1] % mod] * r % mod;
if ( tmp < i && tmp ) {
cout << tmp << " " << i;
return ;
}
}
cout << -1 << " " << -1;
}
signed main () {
#ifdef judge
freopen ( "Code.in", "r", stdin );
freopen ( "Code.out", "w", stdout );
freopen ( "Code.err", "w", stderr );
#endif
Solve ();
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 176ms
memory: 72324kb
input:
65 9096341 8846419
output:
13 18
result:
ok ok
Test #2:
score: 0
Accepted
time: 23ms
memory: 10292kb
input:
8 1155823 0
output:
-1 -1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 1256kb
input:
91 79 78
output:
51 79
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 1256kb
input:
34 19 0
output:
1 2
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 1264kb
input:
2 2 0
output:
-1 -1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 1264kb
input:
100 11 4
output:
-1 -1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 1260kb
input:
80 37 0
output:
1 2
result:
ok ok
Test #8:
score: 0
Accepted
time: 157ms
memory: 59836kb
input:
69 7498201 1018078
output:
23 36
result:
ok ok
Test #9:
score: 0
Accepted
time: 85ms
memory: 31144kb
input:
67 3825511 2142238
output:
-1 -1
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 1260kb
input:
95 61 53
output:
29 61
result:
ok ok
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 117ms
memory: 51004kb
input:
983 6365153 4944288
output:
73 283
result:
ok ok
Test #12:
score: 0
Accepted
time: 80ms
memory: 31020kb
input:
612 3807691 0
output:
-1 -1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 1276kb
input:
744 727 405
output:
57 727
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 1264kb
input:
209 127 0
output:
1 2
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 1260kb
input:
2 2 0
output:
-1 -1
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 1276kb
input:
900 409 78
output:
-1 -1
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 1260kb
input:
624 293 0
output:
1 2
result:
ok ok
Test #18:
score: 0
Accepted
time: 47ms
memory: 20184kb
input:
741 2421109 2171469
output:
21 22
result:
ok ok
Test #19:
score: 0
Accepted
time: 171ms
memory: 63524kb
input:
791 7968479 5501513
output:
-1 -1
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 1260kb
input:
112 89 31
output:
17 89
result:
ok ok
Subtask #3:
score: 60
Accepted
Test #21:
score: 60
Accepted
time: 518ms
memory: 209424kb
input:
8546661 9551959 3193270
output:
2081 5557
result:
ok ok
Test #22:
score: 0
Accepted
time: 714ms
memory: 141100kb
input:
4298159 9302861 0
output:
-1 -1
result:
ok ok
Test #23:
score: 0
Accepted
time: 27ms
memory: 11864kb
input:
513325 422083 392021
output:
259709 422083
result:
ok ok
Test #24:
score: 0
Accepted
time: 54ms
memory: 28996kb
input:
1566540 991871 0
output:
1 2
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 1264kb
input:
2 2 0
output:
-1 -1
result:
ok ok
Test #26:
score: 0
Accepted
time: 482ms
memory: 163140kb
input:
620835803 5180041 4842294
output:
-1 -1
result:
ok ok
Test #27:
score: 0
Accepted
time: 349ms
memory: 158300kb
input:
15765760 5025589 0
output:
1 2
result:
ok ok
Test #28:
score: 0
Accepted
time: 240ms
memory: 106956kb
input:
4306335 4916707 2219367
output:
510 4943
result:
ok ok
Test #29:
score: 0
Accepted
time: 364ms
memory: 153392kb
input:
4843363 9786319 4491526
output:
4829 5056
result:
ok ok
Test #30:
score: 0
Accepted
time: 701ms
memory: 266604kb
input:
15042407 9461099 3361767
output:
5550468 9461099
result:
ok ok
Extra Test:
score: 0
Extra Test Passed