QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#672285	#9485. (mod N² + 1)	masterhuang	AC ✓	9ms	3740kb	C++23	1.5kb	2024-10-24 16:17:43	2024-10-24 16:17:44

Judging History

你现在查看的是最新测评结果

[2024-10-24 16:17:44]
评测

测评结果：AC
用时：9ms
内存：3740kb

查看

[2024-10-24 16:17:43]
提交

answer

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=55;
int T,n,r,p,lg[N*N],pw[N*N],a[N][N];
namespace GG
{
	int n;vector<int>g;
	inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%n),x=1ll*x*x%n,p>>=1);return s;}
	inline bool isy(int x){if(__gcd(x,n)>1) return 0;for(int i:g) if(ksm(x,i)==1) return 0;return 1;}
	inline int gg(int x)
	{
		g.clear();int t=(n=x)-1,y=t;
		for(int i=2;i*i<=y;i++) if(y%i==0){while(y%i==0) y/=i;g.push_back(t/i);}(y^1)&&(g.push_back(t/y),1);
		for(int i=1;i<x;i++) if(isy(i)) return i;
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
	while(T--)
	{
		cin>>n>>r;
		if(n==1){cout<<"Yes\n1\n";continue;}
		if(n==3&&!r){cout<<"Yes\n1 2 3\n4 5 6\n7 8 9\n";continue;}
		p=n*n+1;bool o=1;
		for(int i=2;i*i<=p;i++) if(!(p%i)){o=0;break;}
		if(!o||!r){cout<<"No\n";continue;}int g=GG::gg(p);
		for(int i=0,s=1;i<p-1;i++,s=1ll*s*g%p) lg[pw[i]=s]=i;
		r=lg[r];int cnt=0;
		if((r&3)!=2){cout<<"No\n";continue;}
		for(int i=1;i<=n;i+=2) for(int j=1;j<=n;j+=2) a[i][j]=++cnt;
		for(int i=n-1;i>0;i-=2) for(int j=2;j<=n;j+=2) a[i][j]=++cnt;
		for(int i=2;i<=n;i+=2) for(int j=n-1;j>0;j-=2) a[i][j]=++cnt;
		for(int i=n;i>0;i-=2) for(int j=n;j>0;j-=2) a[i][j]=++cnt;
		int d=(r-2)/4;cout<<"Yes\n";
		for(int i=1;i<=n;i++,cout<<"\n") for(int j=1;j<=n;j++)
			cout<<pw[(a[i][j]+d)%(p-1)]<<" ";
	}
	return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3720kb

input:

output:

Yes
2 4 
3 1 
No
Yes
13 8 5 7 
12 10 4 9 
15 16 11 14 
6 3 2 1

result:

ok Correct Answer

Test #2:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

Yes
2 40 4 80 8 160 16 123 32 49 64 98 128 196 
69 1 133 99 165 148 181 74 189 37 193 117 195 157 
59 185 118 173 39 149 78 101 156 5 115 10 33 20 
164 177 82 187 41 192 119 96 158 48 79 24 138 12 
66 43 132 86 67 172 134 147 71 97 142 194 87 191 
110 6 55 3 126 100 63 50 130 25 65 111 131 154 
174 ...

result:

ok Correct Answer

Test #3:

score: 0

Accepted

time: 2ms

memory: 3584kb

input:

output:

Yes
41 183 123 35 112 105 79 58 237 174 197 8 77 24 231 72 
26 185 180 233 60 249 20 83 178 199 145 152 134 222 216 74 
179 230 23 176 69 14 207 42 107 126 64 121 192 106 62 61 
195 196 65 151 193 136 150 131 50 215 188 243 234 81 78 27 
186 202 44 92 132 19 139 57 160 171 223 256 155 254 208 248 
4...

result:

ok Correct Answer

Test #4:

score: 0

Accepted

time: 3ms

memory: 3708kb

input:

output:

Yes
116 392 348 374 242 320 325 158 173 73 118 219 354 256 260 367 379 299 335 95 
66 306 22 102 141 34 47 145 283 182 228 328 76 243 159 81 53 27 285 9 
203 224 208 271 223 11 268 33 2 99 6 297 18 89 54 267 162 400 85 398 
316 3 239 1 347 134 383 312 395 104 399 302 133 368 178 390 193 130 198 177 ...

result:

ok Correct Answer

Test #5:

score: 0

Accepted

time: 4ms

memory: 3724kb

input:

output:

Yes
196 566 403 522 284 302 266 356 176 49 303 245 361 71 74 355 370 44 119 220 18 523 90 307 
487 270 559 54 458 357 207 533 503 222 216 506 274 332 401 528 311 221 293 275 174 55 381 11 
450 544 519 412 287 329 281 491 251 147 101 158 505 213 217 488 508 132 232 83 6 415 30 344 
547 233 571 162 34...

result:

ok Correct Answer

Test #6:

score: 0

Accepted

time: 4ms

memory: 3572kb

input:

output:

Yes
347 423 17 169 34 338 68 676 136 675 272 673 544 669 411 661 145 645 290 613 580 549 483 421 289 165 
388 512 194 256 97 128 387 64 532 32 266 16 133 8 405 4 541 2 609 1 643 339 660 508 330 254 
578 56 479 112 281 224 562 448 447 219 217 438 434 199 191 398 382 119 87 238 174 476 348 275 19 550 ...

result:

ok Correct Answer

Test #7:

score: 0

Accepted

time: 7ms

memory: 3612kb

input:

output:

Yes
539 460 401 243 125 486 250 295 500 590 323 503 646 329 615 658 553 639 429 601 181 525 362 373 47 69 
630 608 315 304 496 152 248 76 124 38 62 19 31 348 354 174 177 87 427 382 552 191 276 434 138 217 
94 405 188 133 376 266 75 532 150 387 300 97 600 194 523 388 369 99 61 198 122 396 244 115 488...

result:

ok Correct Answer

Test #8:

score: 0

Accepted

time: 3ms

memory: 3596kb

input:

output:

Yes
398 625 89 1062 890 244 1118 1143 804 1054 258 164 1283 343 1157 836 1194 578 267 592 76 732 760 835 1115 568 774 492 1255 1029 877 1211 988 437 801 479 
496 818 309 860 420 86 42 268 523 805 182 729 537 462 1221 565 1030 705 103 719 140 461 14 954 1039 1133 493 243 179 154 407 1053 1208 235 899...

result:

ok Correct Answer

Test #9:

score: 0

Accepted

time: 2ms

memory: 3648kb

input:

output:

Yes
170 1023 403 1151 139 1134 93 964 930 561 221 422 913 329 51 696 510 475 1209 859 417 808 279 298 196 386 663 1266 145 987 153 791 233 128 1033 1280 
264 17 1064 1169 1144 506 1152 310 634 31 1101 911 1018 999 880 489 88 438 787 822 1246 601 384 968 1076 875 367 736 1204 333 1158 163 894 146 112...

result:

ok Correct Answer

Test #10:

score: 0

Accepted

time: 8ms

memory: 3592kb

input:

output:

Yes
608 668 892 195 1138 653 1004 45 961 450 531 609 122 902 1220 1238 527 707 82 585 820 662 418 135 289 53 296 530 366 112 1066 1120 284 824 246 458 
1051 839 1013 473 231 177 931 1185 1001 767 1008 1244 879 1162 477 635 1215 712 770 590 77 59 1175 395 766 688 336 847 293 1252 159 644 405 1102 689...

result:

ok Correct Answer

Test #11:

score: 0

Accepted

time: 9ms

memory: 3740kb

input:

output:

Yes
903 1423 1108 1067 122 1600 366 1598 1098 1592 92 1574 276 1520 828 1358 883 872 1048 1015 1543 1444 1427 1130 1079 188 35 564 105 91 315 273 945 819 1234 856 500 967 1500 1300 
101 301 1101 634 367 745 656 782 1286 1328 1496 1510 1566 1037 522 1413 174 471 58 157 553 586 718 729 773 243 1325 81...

result:

ok Correct Answer

Test #12:

score: 0

Accepted

time: 9ms

memory: 3724kb

input:

output:

Yes
104 944 312 1231 936 491 1207 1473 419 1217 1257 449 569 1347 106 839 318 916 954 1147 1261 239 581 717 142 550 426 49 1278 147 632 441 295 1323 885 767 1054 700 1561 499 
40 1102 547 901 716 834 1306 278 969 1160 323 1454 1175 1552 1459 1051 1020 884 340 1362 647 454 1283 685 1495 762 1032 254 ...

result:

ok Correct Answer

Test #13:

score: 0

Accepted

time: 9ms

memory: 3592kb

input:

output:

Yes
580 1570 139 1508 417 1322 1251 764 551 691 52 472 156 1416 468 1046 1404 1537 1010 1409 1429 1025 1085 1474 53 1220 159 458 477 1374 1431 920 1091 1159 71 275 213 825 639 874 
962 727 1388 776 1530 1326 510 442 170 681 1124 227 1442 1143 1548 381 516 127 172 576 591 192 197 64 1133 555 1445 185...

result:

ok Correct Answer

Test #14:

score: 0

Accepted

time: 5ms

memory: 3580kb

input:

output:

Yes
370 1388 1110 962 128 1285 384 653 1152 358 254 1074 762 20 685 60 454 180 1362 540 884 19 1051 57 1552 171 1454 513 1160 1539 278 1415 834 1043 901 1528 1102 1382 104 944 
1497 657 499 219 700 73 767 558 1323 186 441 62 147 1088 49 1430 550 1544 717 1582 239 1061 1147 1421 916 1541 839 1581 134...

result:

ok Correct Answer

Test #15:

score: 0

Accepted

time: 1ms

memory: 3652kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #16:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #17:

score: 0

Accepted

time: 0ms

memory: 3724kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #18:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #19:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #20:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #21:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #22:

score: 0

Accepted

time: 0ms

memory: 3708kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #23:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #24:

score: 0

Accepted

time: 0ms

memory: 3636kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #25:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

output:

No
No
No
No
Yes
2 4 
3 1 
Yes
1 2 3
4 5 6
7 8 9
No
No
No
No
No
No
No
No
No
No
No
Yes
13 8 5 7 
12 10 4 9 
15 16 11 14 
6 3 2 1 
No
No
No
No
No
Yes
10 14 13 8 
4 9 7 3 
5 11 15 16 
2 1 12 6 
Yes
3 11 9 16 
8 1 14 6 
10 5 13 15 
4 2 7 12 
No
No
No
No
No
Yes
9 16 10 14 
7 3 8 1 
13 15 5 11 
12 6 4 2 
N...

result:

ok Correct Answer

Test #26:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok Correct Answer

Test #27:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
2 82 4 6...

result:

ok Correct Answer

Test #28:

score: 0

Accepted

time: 1ms

memory: 3660kb

input:

output:

No
Yes
14 69 28 37 56 74 11 47 22 94 
79 7 90 54 45 27 73 64 87 32 
44 100 88 99 75 97 49 93 98 85 
3 16 52 8 26 4 13 2 57 1 
95 41 89 82 77 63 53 25 5 50 
96 51 48 76 24 38 12 19 6 60 
10 36 20 72 40 43 80 86 59 71 
42 30 21 15 61 58 81 29 91 65 
17 39 34 78 68 55 35 9 70 18 
31 83 66 92 33 46 67 2...

result:

ok Correct Answer

Extra Test:

score: 0

Extra Test Passed