QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190894#5141. Identical ParitybzwAC ✓63ms3628kbC++111.0kb2023-09-29 15:21:592023-09-29 15:22:00

Judging History

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

  • [2023-09-29 15:22:00]
  • 评测
  • 测评结果：AC
  • 用时：63ms
  • 内存：3628kb
查看
  • [2023-09-29 15:21:59]
  • 提交

answer

// qwq
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=1e6+1;
int T,n,m;
ll gcd(ll a,ll b){return __gcd(abs(a),abs(b));}
void exgcd(ll a,ll b,ll &x,ll& y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,y,x),y-=(a/b)*x;
}
ll a1(ll a,ll b){
    ll t=b/a+1;
    if(t*a<=b)return t;
    t--;
    if(t*a<=b)return t;
    t--;
    if(t*a<=b)return t;
}
ll a2(ll a,ll b){
    ll t=b/a-1;
    if(t*a>=b)return t;
    t++;
    if(t*a>=b)return t;
    t++;
    if(t*a>=b)return t;
}
bool ok(ll a,ll b,ll A,ll C,ll D){
    ll g=gcd(a,b);if(A%g)return 0;
    ll t=A/g,x,y;exgcd(a,b,x,y);x*=t,y*=t;
    ll l1=-x,r1=C-x,d1=b/g;
    ll l2=-y,r2=D-y,d2=a/g;
    swap(l2,r2);l2=-l2,r2=-r2;
    l1=a2(d1,l1),r1=a1(d1,r1);
    l2=a2(d2,l2),r2=a1(d2,r2);
    return max(l1,l2)<=min(r1,r2);
}
int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        int A=n>>1,B=n+1>>1;
        int C=n%m,D=m-C,a=n/m+1,b=n/m;
        puts(ok(a,b,A,C,D)?"Yes":"No");
    }
    return 0;
}
源文件, 语言: C++11

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

3
3 1
4 2
5 3

output:

No
Yes
Yes

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: 0
Accepted
time: 47ms
memory: 3600kb

input:

100000
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
5 1
5 2
5 3
5 4
5 5
6 1
6 2
6 3
6 4
6 5
6 6
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
11 11
12 1
...

output:

Yes
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes...

result:

ok 100000 token(s): yes count is 92971, no count is 7029

Test #3:

score: 0
Accepted
time: 27ms
memory: 3564kb

input:

100000
1 1
9 4
6 4
7 4
6 3
4 2
9 9
4 3
1 1
7 4
1 1
7 7
5 2
6 3
4 4
10 10
9 3
6 6
10 1
9 6
6 6
7 7
6 3
7 7
6 6
3 2
8 8
10 10
7 3
3 1
2 1
7 2
10 10
9 7
1 1
5 1
4 4
8 8
9 9
5 3
4 4
1 1
9 7
7 1
10 2
6 2
8 2
2 1
9 9
8 7
8 3
3 1
5 4
3 3
10 10
8 8
2 1
8 8
10 10
10 3
10 2
2 2
7 7
4 1
10 1
4 2
8 3
8 2
7 7
5 ...

output:

Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes...

result:

ok 100000 token(s): yes count is 70906, no count is 29094

Test #4:

score: 0
Accepted
time: 47ms
memory: 3628kb

input:

100000
24 8
34 34
89 44
53 30
33 33
77 77
16 16
85 85
14 5
75 75
14 9
78 67
53 53
73 10
73 11
44 4
97 31
88 22
99 78
63 54
100 3
11 9
67 12
55 22
63 14
20 10
82 62
75 10
92 1
39 34
77 15
7 7
76 6
45 9
96 48
30 7
4 4
12 11
9 6
76 16
96 18
58 6
8 8
51 10
100 8
69 69
78 74
35 6
77 70
63 63
35 22
20 3
3...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes...

result:

ok 100000 token(s): yes count is 78553, no count is 21447

Test #5:

score: 0
Accepted
time: 27ms
memory: 3624kb

input:

100000
192 41
865 10
277 236
404 298
745 211
762 762
736 711
340 38
489 25
870 105
688 40
160 159
658 649
783 783
477 250
257 18
568 23
395 138
719 359
778 554
124 124
498 5
483 257
267 16
75 21
683 341
127 64
526 10
296 15
487 295
239 15
111 7
253 21
770 14
265 24
389 235
786 504
564 564
411 276
38...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
N...

result:

ok 100000 token(s): yes count is 81455, no count is 18545

Test #6:

score: 0
Accepted
time: 59ms
memory: 3592kb

input:

100000
4003 575
7289 7046
8995 58
1577 733
9173 7729
844 52
8951 1352
7973 3986
5119 3924
4668 4668
7815 5841
739 451
4778 36
2188 2188
3484 1892
9258 66
533 377
9557 69
7404 265
9609 40
1214 1025
5665 812
8127 7347
5342 2671
1625 18
5216 3852
4270 46
5744 4027
8907 7170
3534 3420
7233 3113
8075 807...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes...

result:

ok 100000 token(s): yes count is 83348, no count is 16652

Test #7:

score: 0
Accepted
time: 48ms
memory: 3624kb

input:

100000
94582 94582
69291 14631
46488 10296
59177 160
78974 53928
94307 34407
52245 27037
12683 5798
57630 170
99882 304
48988 48988
42297 18726
67566 262
65662 57867
76780 67428
79156 73214
65758 12352
60103 60103
28738 17248
37409 37409
53728 17909
59800 39782
74537 74537
3041 138
30203 15734
11982...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Y...

result:

ok 100000 token(s): yes count is 84294, no count is 15706

Test #8:

score: 0
Accepted
time: 60ms
memory: 3552kb

input:

100000
50534 647
678283 980
30125 21366
248223 221768
985737 234150
387629 132381
904312 904312
467229 333595
738198 292290
570819 68
587262 766
802340 284
255271 182985
380342 126780
289440 80342
848027 848027
365288 517
41897 41897
248003 296
886340 443170
175494 35804
738204 534958
8090 6685
3621...

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Y...

result:

ok 100000 token(s): yes count is 84672, no count is 15328

Test #9:

score: 0
Accepted
time: 48ms
memory: 3608kb

input:

100000
2542083 1450
9403921 5063511
2365308 2365308
758174 197896
2241490 1430147
9512028 4365809
4107183 4107183
7169208 3907715
840238 1609
4938305 1634705
3322433 2143003
1120341 835487
7189451 180378
6959659 2427714
2342484 612544
3236442 1448232
5289119 3638045
6960961 773440
8543504 2847834
42...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Ye...

result:

ok 100000 token(s): yes count is 84585, no count is 15415

Test #10:

score: 0
Accepted
time: 63ms
memory: 3608kb

input:

100000
71830880 9322064
80071926 80071926
89363353 17872670
96319174 89252167
15049325 5016441
41013329 20506664
77437871 77437871
92179669 92179669
60621300 56656489
18654421 13515950
14765264 2773682
96200712 26642428
71073827 71073827
66241844 5888
90501972 90501972
56743382 56743382
72988225 729...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes...

result:

ok 100000 token(s): yes count is 84313, no count is 15687

Test #11:

score: 0
Accepted
time: 54ms
memory: 3536kb

input:

100000
821007425 800981403
435890607 272139740
758767172 758767172
762585330 603506952
887544309 443772154
491408241 370843726
709855901 377017800
431184519 431184519
42591965 30895770
383393427 201656162
859876627 429938313
836615393 779400955
528836154 424440898
629793696 629793696
604863713 12242...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100000 token(s): yes count is 84521, no count is 15479
English 繁體中文 简体中文

服务器时间: 2024-12-11 21:42:01 | 开源项目