UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210237#3789. 我可能是C题_Alexande_1004305ms266604kbC++112.5kb2024-08-06 09:37:252024-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