NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #206450 | #3165. 方程的解 | FHL | 100 | 4363ms | 5020kb | C++11 | 650b | 2024-07-22 18:56:56 | 2024-07-22 20:11:00 |
answer
#include <cstdio>
#include <cmath>
#include <map>
#define int long long
using namespace std;
int T;
int solve(int a, int b, int p) {
map<int, int> m;
int mulm = 1, t = sqrt(p) + 1;
for (int i = 1; i <= t; i ++ ) {
mulm = mulm * a % p;
m[b * mulm % p] = i;
}
int now = mulm;
for (int i = 1; i <= t; i ++ ) {
if (m[now]) return (int)i * t - m[now];
now = now * mulm % p;
}
return -1;
}
signed main() {
scanf("%lld", &T);
while (T -- ) {
int p, a, b;
scanf("%lld%lld%lld", &p, &a, &b);
int ans = solve(a, b, p);
if (ans == -1) printf("no solution\n");
else printf("%lld\n", ans);
}
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 4ms
memory: 1124kb
input:
40 38371 30278 12451 51949 1925 16824 39727 8424 23446 35729 8604 4699 48221 3464 35984 99961 3104 7...
output:
no solution 12246 no solution 26865 5259 53994 no solution no solution no solution 62082 34527 no so...
result:
ok 40 lines
Test #2:
score: 10
Accepted
time: 4ms
memory: 1124kb
input:
40 59797 57209 1596 88771 8724 31857 1409 750 657 92669 11315 62 35809 28252 29433 9433 6982 6988 71...
output:
no solution 17394 187 no solution no solution no solution 10863 5469 no solution no solution 11450 1...
result:
ok 40 lines
Test #3:
score: 10
Accepted
time: 5ms
memory: 1124kb
input:
40 27737 16262 21614 74101 65654 72418 95063 80940 29105 37171 6120 13141 59467 6421 48202 67523 125...
output:
2442 no solution 18376 16604 no solution 9491 28584 32526 61895 81785 1498 3972 36718 no solution 25...
result:
ok 40 lines
Test #4:
score: 10
Accepted
time: 650ms
memory: 4900kb
input:
40 701007721 226836410 700221467 609376637 555505065 537110248 718126649 27666056 209669407 72722314...
output:
661928284 no solution no solution no solution 176718 no solution no solution 44398418 202453465 3013...
result:
ok 40 lines
Test #5:
score: 10
Accepted
time: 444ms
memory: 4900kb
input:
40 998347159 951648148 222699374 265346579 170041583 1651913 854282311 697467218 708280399 593929477...
output:
221559601 236087167 180546784 no solution 178292130 788810105 471022049 111588212 26971634 no soluti...
result:
ok 40 lines
Test #6:
score: 10
Accepted
time: 520ms
memory: 4948kb
input:
40 508928911 368260395 197014976 467174443 20166302 457682957 633266987 365520218 142332172 99393132...
output:
78428882 no solution 126879376 282180619 212652957 no solution no solution 71081001 no solution no s...
result:
ok 40 lines
Test #7:
score: 10
Accepted
time: 644ms
memory: 5020kb
input:
40 566551577 461319 143876378 626673361 94961490 614207471 319184081 208898009 250733304 79134857 67...
output:
42699350 no solution no solution 31308962 no solution 75601139 2556315 no solution 108622155 5470549...
result:
ok 40 lines
Test #8:
score: 10
Accepted
time: 698ms
memory: 4916kb
input:
40 781753457 121430598 605906664 611135243 389418731 471876973 43073521 11878623 36994297 600303173 ...
output:
476544225 59696004 13371203 103927676 no solution 212232978 no solution 8137839 no solution 7640582 ...
result:
ok 40 lines
Test #9:
score: 10
Accepted
time: 696ms
memory: 4960kb
input:
40 558435851 475491008 117732431 855534541 258937944 550324527 786565141 437830687 631195882 9550869...
output:
96234018 no solution no solution 828878625 608502042 no solution no solution no solution 13898141 no...
result:
ok 40 lines
Test #10:
score: 10
Accepted
time: 698ms
memory: 4988kb
input:
40 195720619 179620823 21069142 271820323 34487272 246686683 529565051 417816976 185673874 974626363...
output:
4939877 92699274 no solution no solution no solution 245484712 532725991 706946635 no solution no so...
result:
ok 40 lines
Extra Test:
score: 0
Extra Test Passed
