QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#660728#7735. Primitive RootD06TL 875ms3684kbC++14982b2024-10-20 13:00:472024-10-20 13:00:48

Judging History

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

  • [2024-10-20 13:00:48]
  • 评测
  • 测评结果：TL
  • 用时：875ms
  • 内存：3684kb
查看
  • [2024-10-20 13:00:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long T;
	cin>>T;
	while(T--)
	{
		long long p,m;
		cin>>p>>m;
		long long ans=0;
		long long x=0,cur=1;
		while(p>=cur)
		{
			x++;
			cur*=2;
		}
		long long i;
		ans=ans+((m/cur-1)/p)*(2+max(0ll,((p-1)-max((p-cur+2),0ll)+1))+max(0ll,((p-1)-max((2*p-cur+2),0ll)+1)));
		i=(m/cur-1)/p*p;
		for(i;i<=m/cur-1;i++)
		{
			if(i*cur%p<=1)
			{
				ans++;
			}
			if(i*cur%p>=p-cur+2)
			{
				ans++;
			}
			if(i*cur%p>=2*p-cur+2)
			{
				ans++;
			}
		}
		/*
		long long tmp=((i*cur)^(p-1))%p;
		if(1-tmp>=0&&(1-tmp^(p-1))<=m%cur)
		{
			ans++;
		}
		if(p+1-tmp>=0&&((p+1-tmp)^(p-1))<=m%cur)
		{
			ans++;
		}
		if(2*p+1-tmp>=0&&((2*p+1-tmp)^(p-1))<=m%cur)
		{
			ans++;
		}
		*/
		for(long long j=0;i*cur+j<=m;j++)
		{
			if(((i*cur+j)^(p-1))%p==1)
			{
				ans++;
			}
		}
		
		cout<<ans<<endl;
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
2 0
7 11
1145141 998244353

output:

1
2
872

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 28ms
memory: 3484kb

input:

47595
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
2 22
2 23
2 24
2 25
2 26
2 27
2 28
2 29
2 30
2 31
2 32
2 33
2 34
2 35
2 36
2 37
2 38
2 39
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 47
2 48
2 49
2 50
2 51
2 52
2 53
2 54
2 55
2 56
2 57
2 58
2 59
2 60...

output:

1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
49
50
50
51
51
52
52
53
53
...

result:

ok 47595 lines

Test #3:

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

input:

100000
11 34
71 35
11 45
53 28
3 67
17 38
41 2
23 8
47 26
79 98
89 47
97 33
43 95
97 98
29 79
29 48
67 27
37 3
97 72
71 97
67 53
23 77
71 12
101 92
89 63
61 71
59 94
97 2
29 64
53 74
47 78
67 0
97 66
79 81
3 48
67 87
79 88
59 63
17 25
61 37
67 64
79 93
67 92
89 0
59 88
11 29
29 5
13 47
101 80
3 12
8...

output:

3
1
5
1
23
3
1
0
0
2
1
1
2
2
4
3
1
1
1
2
1
4
0
1
1
3
3
1
3
2
2
0
1
2
16
2
2
2
2
1
1
2
2
0
3
3
1
4
1
4
1
1
14
45
1
1
3
1
4
2
1
2
1
1
2
1
8
2
1
2
1
1
0
1
2
2
1
3
3
9
1
2
1
1
32
1
1
2
1
1
0
1
4
1
1
3
1
2
1
2
2
1
0
2
3
0
1
1
1
3
2
2
1
5
4
1
1
3
2
0
3
2
3
1
6
1
2
9
0
2
2
3
1
1
2
1
2
2
1
1
0
2
2
12
21
4
3...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 50ms
memory: 3568kb

input:

100000
29 83
47 14
29 56
2 29
17 35
67 31
3 24
97 39
17 5
59 16
53 51
29 51
67 72
53 14
79 54
11 35
83 56
89 11
5 70
67 42
89 65
7 40
41 45
79 13
7 26
5 51
5 49
47 46
19 2
89 74
47 27
71 37
37 39
83 86
7 86
71 15
29 94
19 17
101 56
23 3
59 95
97 73
11 15
29 66
23 23
23 51
53 95
11 95
61 0
97 14
73 5...

output:

4
0
3
15
2
1
8
1
1
1
1
3
2
1
1
3
1
1
15
1
1
6
2
0
4
10
10
1
0
1
0
1
2
2
13
1
4
1
1
0
3
1
2
3
2
2
3
9
0
1
1
2
4
0
1
1
2
1
11
2
1
2
3
1
1
1
3
3
1
1
2
1
1
1
1
1
5
8
1
4
9
0
3
1
14
2
1
2
2
1
6
3
1
5
1
1
3
1
2
10
1
2
4
2
1
1
1
1
1
1
4
3
1
5
1
1
2
1
1
1
2
1
6
2
1
0
7
0
1
2
2
4
2
1
1
2
3
1
3
1
1
1
3
1
6
3
...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 40ms
memory: 3616kb

input:

100000
59 60
97 9
53 69
7 58
71 67
3 88
61 92
83 42
67 64
71 43
29 30
83 31
89 89
47 93
67 90
97 74
11 80
89 84
47 38
19 43
67 55
59 15
101 68
71 58
97 40
73 94
71 88
89 8
67 35
37 81
31 24
23 58
73 51
43 34
71 88
41 69
37 37
7 2
79 79
97 65
17 89
41 78
31 3
97 37
7 91
47 95
97 33
97 60
37 74
29 83
...

output:

2
1
2
8
1
29
3
1
1
1
2
1
2
2
2
1
8
1
1
3
1
1
1
1
1
2
2
1
1
2
0
3
1
1
2
2
2
0
2
1
6
2
0
1
14
2
1
1
2
4
5
0
5
1
2
1
1
1
0
1
1
0
7
17
2
7
3
1
0
0
1
1
8
3
1
2
1
1
1
1
0
1
1
7
4
2
7
5
0
1
21
3
1
1
0
3
0
0
2
1
1
1
2
5
6
4
1
2
1
1
2
1
4
1
1
2
21
0
3
1
5
1
20
1
2
1
3
5
0
0
6
3
1
2
5
0
1
3
8
2
1
3
1
1
3
1
1
...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 875ms
memory: 3492kb

input:

100000
1861 3528
2333 9090
2579 5653
8147 4315
1381 1926
1213 8598
7681 7742
5039 8270
7927 3661
2819 9458
7229 4213
683 8300
787 4660
7753 1678
7283 9943
6029 2737
5051 6439
9371 9827
1277 5268
2753 5913
5437 1537
2851 4021
1289 1807
6529 7605
7949 9316
8101 2770
6451 2437
2039 1348
1307 6586
9011 ...

output:

3
4
3
1
2
8
2
2
1
3
1
13
7
1
3
1
2
2
4
2
1
2
2
2
3
1
1
1
5
1
2
1
1
1
1
14
6
4
1
1
1
2
1
1
2
23
1
32
1
2
7
4
1
2
3
1
2
2
4
1
9
1
4
3
4
1
5
3
2
2
4
123
1
2
9
1
1
3
1
1
2
1
3
1
1
4
3
1
1
1
1
1
1
1
1
3
1
1
4
4
1
3
1
18
1
11
1
2
2
1
3
1
1
0
329
1
1
2
3
1
2
1
1
4
1
1
2
4
5
1
3
1
7
2
1
1
2
1
2
2
2
1
1
1
2
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 866ms
memory: 3684kb

input:

100000
2861 7238
2411 6690
1951 8793
7877 4503
7237 6677
8311 2550
9883 8304
233 2207
9397 6356
907 7980
7591 192
7643 9101
8963 3945
5683 436
6007 4005
3299 123
1103 5136
9719 9329
2099 1890
7793 6195
2203 8339
4057 9237
5521 3288
6733 7011
563 5121
2879 8277
9091 124
1913 229
307 7781
1801 7702
67...

output:

2
3
6
1
1
1
1
9
1
9
1
2
1
1
1
1
5
1
1
1
4
4
1
2
10
3
1
1
27
5
1
5
1
2
3
2
1
1
22
2
2
1
1
2
1
1
1
1
1
2
1
1
1
4
1
1
18
1
4
11
42
1
3
2
1
2
2
2
1
1
6
1
2
1
1
3
1
1
13
35
1
1
1
1
1
1
3
2
1
1
1
1
7
1
1
1
5
1
1
2
3
1
1
1
1
2
1
1
5
1
4
6
2
1
51
1
1
8
4
3
13
31
5
2
1
50
1
2
1
1
3
19
1
1
2
13
3
1
1
3
1
2
1
...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 842ms
memory: 3556kb

input:

100000
7177 7208
2753 1599
2909 8176
6547 7781
2543 4318
7177 3366
127 1355
7283 479
6073 6686
3847 195
6761 3446
2099 2392
2609 4676
3637 3268
8849 7603
5179 7731
827 7446
3163 299
9461 8223
6581 8750
4373 9228
9187 8667
2963 6819
4057 7322
5059 9167
9041 3320
9151 8842
2153 6137
1993 6329
4517 606...

output:

2
1
3
2
2
1
12
1
2
1
1
2
2
1
1
2
9
1
1
2
3
1
2
3
2
1
1
3
4
2
2
1
2
1
2
16
1
5
1
1
40
1
1
1
1
30
1
3
2
1
3
3
2
2
4
10
2
9
1
2
1
1
2
1
3
1
1
1
6
2
1
1
2
4
3
1
1
2
1
1
2
2
1
1
2
2
3
1
1
1
1
6
1
2
3
1
6
1
1
2
1
1
1
1
5
2
1
2
2
5
1
3
1
2
2
1
3
47
7
4
1
1
2
1
3
1
1
3
2
2
7
18
1
1
1
1
1
2
5
3
2
1
1
1
1
3
1...

result:

ok 100000 lines

Test #9:

score: -100
Time Limit Exceeded

input:

100000
22957699 627925429
433183259 202804355
816810829 985631258
54563549 847625650
712837669 860468289
452708161 516705387
541041323 722654987
456499961 122097506
110566411 638241209
103870223 415782860
591063689 459421060
851704643 560244670
491675827 960606500
724808879 813870033
513057607 82205...

output:

27
1

result:
English 繁體中文 简体中文

Server Time: 2024-12-08 12:44:42 | OpenSource Project