XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#59325 #1304. zxh的派系共识 Accepted 100 166 ms 468 K C++ 17 / 1.6 K 丁丁跑卡车 2021-07-14 20:43:05
显示原始代码 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ud unsigned int
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
//#define pi 3.141592653589
#define eps 1e-9
#define F(x) ((x) / 3 + ((x) % 3 == 1 ? 0 : tb))
#define G(x) ((x) < tb ? (x)*3 + 1 : ((x)-tb) * 3 + 2)
//#define p 2173412051LL
//#define sz 2

using namespace std;

template <typename T>
void read(T &x) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while (!isdigit(ch)) {
        if (ch == '-')
            f *= -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

ll getPhi(ll);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    ll n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        cout << getPhi(m / __gcd(n, m)) << '\n';
    }
    return 0;
}

ll getPhi(ll x) {
    ll res = x;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1)
        res = res / x * (x - 1);
    return res;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：6 ms
内存：468 KiB

输入文件（1.in） 

3
4 9
5 10
42 9999999967

答案文件（1.out） 

6
1
9999999966

用户输出 

6
1
9999999966

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（2.in） 

10
1 2
1 3
1 4
3 5
3 6
3 7
1 8
7 9
8 10
1 11

答案文件（2.out） 

1
2
2
4
1
6
4
6
4
10

用户输出 

1
2
2
4
1
6
4
6
4
10

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（3.in） 

10
20 52
48 53
36 54
23 55
14 56
54 57
34 58
33 59
10 60
21 61

答案文件（3.out） 

12
52
2
40
2
18
28
58
2
60

用户输出 

12
52
2
40
2
18
28
58
2
60

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（4.in） 

10
37 102
78 103
31 104
7 105
80 106
52 107
26 108
1 109
40 110
85 111

答案文件（4.out） 

32
102
48
8
52
106
18
108
10
72

用户输出 

32
102
48
8
52
106
18
108
10
72

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（5.in） 

10
119 152
144 153
41 154
69 155
57 156
91 157
21 158
54 159
105 160
79 161

答案文件（5.out） 

72
16
60
120
24
156
78
52
16
132

用户输出 

72
16
60
120
24
156
78
52
16
132

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（6.in） 

10
36 202
79 203
4 204
140 205
73 206
41 207
61 208
200 209
118 210
75 211

答案文件（6.out） 

100
168
32
40
102
132
96
180
48
210

用户输出 

100
168
32
40
102
132
96
180
48
210

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（7.in） 

10
164 252
94 253
171 254
196 255
35 256
174 257
251 258
239 259
9 260
98 261

答案文件（7.out） 

36
220
126
128
128
256
84
216
96
168

用户输出 

36
220
126
128
128
256
84
216
96
168

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：51 ms
内存：372 KiB

输入文件（8.in） 

50
5882304938 9999763901
9505722760 9999966511
5805364980 9999170087
9810619921 9999771101
5506
<1048 bytes omitted>

答案文件（8.out） 

9999563904
9999766512
9998970096
9999571104
9998374464
9998975376
9998581824
9999783360
9998
<500 bytes omitted>

用户输出 

9999563904
9999766512
9998970096
9999571104
9998374464
9998975376
9998581824
9999783360
9998386608
9998787040
9996793200
9997393
<422 bytes omitted>

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：51 ms
内存：380 KiB

输入文件（9.in） 

50
6891776487 9999998023
4734215850 9999998027
3759181425 9999998083
3605139012 9999998123
3468
<1047 bytes omitted>

答案文件（9.out） 

9999998022
9999998026
9999998082
9999998122
9999998136
9999998146
9999998148
9999998158
9999
<500 bytes omitted>

用户输出 

9999998022
9999998026
9999998082
9999998122
9999998136
9999998146
9999998148
9999998158
9999998190
9999998230
9999998232
9999998
<422 bytes omitted>

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：7 ms
内存：376 KiB

输入文件（10.in） 

50
3196991747 7556064528
1046365130 8269632992
610034468 4621492906
5332350866 6827878205
27612
<1024 bytes omitted>

答案文件（10.out） 

2370525696
2067408240
2279092320
5453181136
5654536848
1899912960
420206400
1159047360
31260
<483 bytes omitted>

用户输出 

2370525696
2067408240
2279092320
5453181136
5654536848
1899912960
420206400
1159047360
3126014640
198097920
1647682560
398097504
<405 bytes omitted>

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（11.in） 

50
3235271017 5751345600
6117973023 6299092800
650281279 6518191680
5197907098 6616209600
34383
<1045 bytes omitted>

答案文件（11.out） 

104509440
364953600
1114767360
597196800
18247680
8257536
11197440
1393459200
681246720
232
<431 bytes omitted>

用户输出 

104509440
364953600
1114767360
597196800
18247680
8257536
11197440
1393459200
681246720
232243200
91238400
6082560
774144000
541
<353 bytes omitted>

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（12.in） 

50
6983776799 6983776800
6983776799 6983776800
6983776799 6983776800
6983776799 6983776800
6983
<1052 bytes omitted>

答案文件（12.out） 

1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194
<500 bytes omitted>

用户输出 

1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393600
1194393
<422 bytes omitted>

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：3 ms
内存：368 KiB

输入文件（13.in） 

50
9311702399 9311702400
9311702399 9311702400
9311702399 9311702400
9311702399 9311702400
9311
<1052 bytes omitted>

答案文件（13.out） 

1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592
<500 bytes omitted>

用户输出 

1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524800
1592524
<422 bytes omitted>

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：4 ms
内存：372 KiB

输入文件（14.in） 

50
240158472 240160776
240155112 240160776
240040824 240160776
240040968 240160776
240063864 24
<894 bytes omitted>

答案文件（14.out） 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698

<397 bytes omitted>

用户输出 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698
10006602
10006602
10006602
10006602
19
<319 bytes omitted>

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：5 ms
内存：320 KiB

输入文件（15.in） 

50
10006603 10006699
10006463 10006699
10001701 10006699
10001707 10006699
10002661 10006699
1
<764 bytes omitted>

答案文件（15.out） 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698

<397 bytes omitted>

用户输出 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698
10006602
10006602
10006602
10006602
19
<319 bytes omitted>

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：4 ms
内存：372 KiB

输入文件（16.in） 

50
5123380736 5123429888
5123309056 5123429888
5120870912 5123429888
5120873984 5123429888
5121
<994 bytes omitted>

答案文件（16.out） 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698

<397 bytes omitted>

用户输出 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698
10006602
10006602
10006602
10006602
19
<319 bytes omitted>

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：4 ms
内存：368 KiB

输入文件（17.in） 

50
2431604529 2431627857
2431570509 2431627857
2430413343 2431627857
2430414801 2431627857
2430
<994 bytes omitted>

答案文件（17.out） 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698

<397 bytes omitted>

用户输出 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698
10006602
10006602
10006602
10006602
19
<319 bytes omitted>

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：4 ms
内存：376 KiB

输入文件（18.in） 

50
1200792360 1200803880
1200775560 1200803880
1200204120 1200803880
1200204840 1200803880
1200
<978 bytes omitted>

答案文件（18.out） 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698

<397 bytes omitted>

用户输出 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698
10006602
10006602
10006602
10006602
19
<319 bytes omitted>

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：4 ms
内存：372 KiB

输入文件（19.in） 

50
1250825375 1250837375
1250807875 1250837375
1250212625 1250837375
1250213375 1250837375
1250
<978 bytes omitted>

答案文件（19.out） 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698

<397 bytes omitted>

用户输出 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698
10006602
10006602
10006602
10006602
19
<319 bytes omitted>

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：4 ms
内存：248 KiB

输入文件（20.in） 

50
2501650750 2501674750
2501615750 2501674750
2500425250 2501674750
2500426750 2501674750
2500
<994 bytes omitted>

答案文件（20.out） 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698

<397 bytes omitted>

用户输出 

10006698
10006698
10006698
10006698
10006698
19260816
10006698
10006698
10006698
10006698
10006602
10006602
10006602
10006602
19
<319 bytes omitted>

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.