XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#80923 #1125. zxh的国土无双 Accepted 100 621 ms 5632 K C++ 11 / 2.2 K 规培005 贺晓珉 2022-08-04 10:13:11
显示原始代码 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int m;
int phi[1000010], prime[1000010], primetot;
bool mark[1000010];
void getphi(int m) {
    phi[1] = 1;
    for (int i = 2; i <= m; i = i + 1) {
        if (!mark[i]) {
            prime[++primetot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= primetot; j = j + 1) {
            if ((ll)i * prime[j] > m)
                break;
            mark[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * (prime[j]);
                break;
            } else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

typedef pair<ll, ll> pr;
pr s[3][40];
int cnt[3];
ll x, y;
vector<ll> vec;
vector<pr> ans;

int check(ll x, ll y) {
    ll xx = x;
    for (int i = 1; i <= primetot; i = i + 1) {
        if (x % prime[i] == 0) {
            s[1][++cnt[1]] = make_pair(prime[i], 1);
            while (x % prime[i] == 0) x /= prime[i], s[1][cnt[1]].second *= prime[i];
        }
    }
    if (x != 1)
        s[1][++cnt[1]] = make_pair(x, x);
    for (int i = 1; i <= primetot; i = i + 1) {
        if (y % prime[i] == 0) {
            s[2][++cnt[2]] = make_pair(prime[i], 1);
            while (y % prime[i] == 0) y /= prime[i], s[2][cnt[2]].second *= prime[i];
        }
    }
    if (y != 1)
        s[2][++cnt[2]] = make_pair(y, y);
    bool chk = 1;
    for (int i = 1; i <= cnt[1]; i++) {
        int flag = 0;
        for (int j = 1; j <= cnt[2]; j++)
            if (s[1][i].first == s[2][j].first && s[1][i].second <= s[2][j].second) {
                flag = 1;
                s[2][j].second /= s[1][i].second;
                /*if(s[2][j].second != 1)
                        vec.push_back(s[2][j].second);*/
            }
        chk &= flag;
    }
    for (int i = 1; i <= cnt[2]; i++)
        if (s[2][i].second != 1)
            vec.push_back(s[2][i].second);
    if (!chk)
        return 0;
    int sz = vec.size();
    for (int i = 0; i < (1 << sz); i++) {
        ll x1 = xx, x2 = xx;
        for (int j = 0; j < sz; j++)
            if ((i >> j) & 1)
                x1 = x1 * vec[j];
            else
                x2 = x2 * vec[j];
        ans.push_back(make_pair(x1, x2));
    }
    return ans.size();
}
int main() {
    getphi(1000000);
    scanf("%lld%lld", &x, &y);
    printf("%d\n", check(x, y));
    for (pr v : ans) printf("%lld %lld\n", v.first, v.second);

    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：14 ms
内存：5576 KiB

输入文件（1.in） 

1000 32000

答案文件（1.out） 

2
1000 32000
32000 1000

用户输出 

2
1000 32000
32000 1000

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（2.in） 

1000 11600

答案文件（2.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（3.in） 

7700 72000

答案文件（3.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（4.in） 

19260817 998244353

答案文件（4.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（5.in） 

24000 24000

答案文件（5.out） 

1
24000 24000

用户输出 

1
24000 24000

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（6.in） 

283 834468949839

答案文件（6.out） 

8
283 834468949839
834468949839 283
849 278156316613
278156316613 849
1981 119209849977
119209
<49 bytes omitted>

用户输出 

8
283 834468949839
849 278156316613
1981 119209849977
5943 39736616659
39736616659 5943
119209849977 1981
278156316613 849
83446
<12 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（7.in） 

44 454817853336

答案文件（7.out） 

32
44 454817853336
454817853336 44
88 227408926668
227408926668 88
132 151605951112
1516059511
<456 bytes omitted>

用户输出 

32
44 454817853336
88 227408926668
132 151605951112
264 75802975556
308 64973979048
616 32486989524
924 21657993016
1848 1082899
<395 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（8.in） 

125 303851909375

答案文件（8.out） 

16
125 303851909375
303851909375 125
3125 12154076375
12154076375 3125
8375 4535103125
4535103
<186 bytes omitted>

用户输出 

16
125 303851909375
3125 12154076375
42875 885865625
1071875 35434625
8375 4535103125
209375 181404125
2872625 13221875
71815625
<141 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（9.in） 

457 368538658068

答案文件（9.out） 

128
457 368538658068
368538658068 457
1371 122846219356
122846219356 1371
1828 92134664517
921
<2243 bytes omitted>

用户输出 

128
457 368538658068
1828 92134664517
1371 122846219356
5484 30711554839
3199 52648379724
12796 13162094931
9597 17549459908
383
<2086 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（10.in） 

447 762459896586

答案文件（10.out） 

16
447 762459896586
762459896586 447
894 381229948293
381229948293 894
19221 17731625502
17731
<196 bytes omitted>

用户输出 

16
447 762459896586
894 381229948293
19221 17731625502
38442 8865812751
917691 371388162
1835382 185694081
39460713 8636934
7892
<151 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（11.in） 

1 953671355196

答案文件（11.out） 

64
1 953671355196
953671355196 1
3 317890451732
317890451732 3
4 238417838799
238417838799 4

<928 bytes omitted>

用户输出 

64
1 953671355196
4 238417838799
3 317890451732
12 79472612933
7 136238765028
28 34059691257
21 45412921676
84 11353230419
41 23
<835 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（12.in） 

1 75953824090

答案文件（12.out） 

32
1 75953824090
75953824090 1
2 37976912045
37976912045 2
5 15190764818
15190764818 5
10 759
<378 bytes omitted>

用户输出 

32
1 75953824090
2 37976912045
5 15190764818
10 7595382409
193 393543130
386 196771565
965 78708626
1930 39354313
1999 37995910

<317 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（13.in） 

2 959796438278

答案文件（13.out） 

8
2 959796438278
959796438278 2
118 16267736242
16267736242 118
55166 34796666
34796666 55166
<33 bytes omitted>

用户输出 

8
2 959796438278
118 16267736242
55166 34796666
3254794 589774
589774 3254794
34796666 55166
16267736242 118
959796438278 2

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（14.in） 

1 612720601101

答案文件（14.out） 

8
1 612720601101
612720601101 1
7 87531514443
87531514443 7
9 68080066789
68080066789 9
63 97
<25 bytes omitted>

用户输出 

8
1 612720601101
9 68080066789
7 87531514443
63 9725723827
9725723827 63
87531514443 7
68080066789 9
612720601101 1

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（15.in） 

1 571168626590

答案文件（15.out） 

64
1 571168626590
571168626590 1
2 285584313295
285584313295 2
5 114233725318
114233725318 5

<912 bytes omitted>

用户输出 

64
1 571168626590
2 285584313295
5 114233725318
10 57116862659
47 12152523970
94 6076261985
235 2430504794
470 1215252397
139 41
<819 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（16.in） 

1 816033297854

答案文件（16.out） 

4
1 816033297854
816033297854 1
2 408016648927
408016648927 2

用户输出 

4
1 816033297854
2 408016648927
408016648927 2
816033297854 1

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（17.in） 

1 722299806965

答案文件（17.out） 

8
1 722299806965
722299806965 1
5 144459961393
144459961393 5
11 65663618815
65663618815 11
5
<31 bytes omitted>

用户输出 

8
1 722299806965
5 144459961393
11 65663618815
55 13132723763
13132723763 55
65663618815 11
144459961393 5
722299806965 1

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（18.in） 

9 801129705372

答案文件（18.out） 

4
9 801129705372
801129705372 9
36 200282426343
200282426343 36

用户输出 

4
9 801129705372
36 200282426343
200282426343 36
801129705372 9

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（19.in） 

1 456969613602

答案文件（19.out） 

16
1 456969613602
456969613602 1
2 228484806801
228484806801 2
3 152323204534
152323204534 3

<156 bytes omitted>

用户输出 

16
1 456969613602
2 228484806801
3 152323204534
6 76161602267
17 26880565506
34 13440282753
51 8960188502
102 4480094251
4480094
<111 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（20.in） 

1 624379090109

答案文件（20.out） 

2
1 624379090109
624379090109 1

用户输出 

2
1 624379090109
624379090109 1

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（21.in） 

1 344111137370

答案文件（21.out） 

1024
1 344111137370
344111137370 1
2 172055568685
172055568685 2
5 68822227474
68822227474 5

<15818 bytes omitted>

用户输出 

1024
1 344111137370
2 172055568685
5 68822227474
10 34411113737
7 49158733910
14 24579366955
35 9831746782
70 4915873391
11 3128
<14765 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（22.in） 

1 947358776276

答案文件（22.out） 

256
1 947358776276
947358776276 1
4 236839694069
236839694069 4
11 86123525116
86123525116 11
<3995 bytes omitted>

用户输出 

256
1 947358776276
4 236839694069
11 86123525116
44 21530881279
23 41189512012
92 10297378003
253 3744501092
1012 936125273
47 2
<3710 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（23.in） 

1 740168683044

答案文件（23.out） 

512
1 740168683044
740168683044 1
3 246722894348
246722894348 3
4 185042170761
185042170761 4
<8027 bytes omitted>

用户输出 

512
1 740168683044
4 185042170761
3 246722894348
12 61680723587
7 105738383292
28 26434595823
21 35246127764
84 8811531941
19 38
<7486 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（24.in） 

1 844023861030

答案文件（24.out） 

1024
1 844023861030
844023861030 1
2 422011930515
422011930515 2
3 281341287010
281341287010 3
<16214 bytes omitted>

用户输出 

1024
1 844023861030
2 422011930515
3 281341287010
6 140670643505
5 168804772206
10 84402386103
15 56268257402
30 28134128701
7 1
<15161 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（25.in） 

1 789491706234

答案文件（25.out） 

1024
1 789491706234
789491706234 1
2 394745853117
394745853117 2
3 263163902078
263163902078 3
<16190 bytes omitted>

用户输出 

1024
1 789491706234
2 394745853117
3 263163902078
6 131581951039
7 112784529462
14 56392264731
21 37594843154
42 18797421577
11 
<15137 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（26.in） 

1 776505385110

答案文件（26.out） 

1024
1 776505385110
776505385110 1
2 388252692555
388252692555 2
3 258835128370
258835128370 3
<16176 bytes omitted>

用户输出 

1024
1 776505385110
2 388252692555
3 258835128370
6 129417564185
5 155301077022
10 77650538511
15 51767025674
30 25883512837
7 1
<15123 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（27.in） 

1 433304299740

答案文件（27.out） 

1024
1 433304299740
433304299740 1
3 144434766580
144434766580 3
4 108326074935
108326074935 4
<15914 bytes omitted>

用户输出 

1024
1 433304299740
4 108326074935
3 144434766580
12 36108691645
5 86660859948
20 21665214987
15 28886953316
60 7221738329
13 33
<14861 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（28.in） 

1 348510998660

答案文件（28.out） 

512
1 348510998660
348510998660 1
4 87127749665
87127749665 4
5 69702199732
69702199732 5
11 
<7859 bytes omitted>

用户输出 

512
1 348510998660
4 87127749665
5 69702199732
20 17425549933
11 31682818060
44 7920704515
55 6336563612
220 1584140903
17 20500
<7318 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（29.in） 

1 642016938420

答案文件（29.out） 

1024
1 642016938420
642016938420 1
4 160504234605
160504234605 4
5 128403387684
128403387684 5
<16086 bytes omitted>

用户输出 

1024
1 642016938420
4 160504234605
9 71335215380
36 17833803845
5 128403387684
20 32100846921
45 14267043076
180 3566760769
11 5
<15033 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（30.in） 

1 200560490130

答案文件（30.out） 

2048
1 200560490130
200560490130 1
2 100280245065
100280245065 2
3 66853496710
66853496710 3

<31252 bytes omitted>

用户输出 

2048
1 200560490130
2 100280245065
3 66853496710
6 33426748355
5 40112098026
10 20056049013
15 13370699342
30 6685349671
7 28651
<29175 bytes omitted>

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（31.in） 

341353499290 682706998580

答案文件（31.out） 

2
341353499290 682706998580
682706998580 341353499290

用户输出 

2
341353499290 682706998580
682706998580 341353499290

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（32.in） 

545434896413 545434896413

答案文件（32.out） 

1
545434896413 545434896413

用户输出 

1
545434896413 545434896413

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（33.in） 

404822138341 809644276682

答案文件（33.out） 

2
404822138341 809644276682
809644276682 404822138341

用户输出 

2
404822138341 809644276682
809644276682 404822138341

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（34.in） 

277417427092 277417427092

答案文件（34.out） 

1
277417427092 277417427092

用户输出 

1
277417427092 277417427092

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（35.in） 

347710816904 695421633808

答案文件（35.out） 

2
347710816904 695421633808
695421633808 347710816904

用户输出 

2
347710816904 695421633808
695421633808 347710816904

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（36.in） 

28150115079 478551956343

答案文件（36.out） 

2
28150115079 478551956343
478551956343 28150115079

用户输出 

2
28150115079 478551956343
478551956343 28150115079

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（37.in） 

99787625634 498938128170

答案文件（37.out） 

2
99787625634 498938128170
498938128170 99787625634

用户输出 

2
99787625634 498938128170
498938128170 99787625634

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（38.in） 

16535387753 198424653036

答案文件（38.out） 

4
16535387753 198424653036
198424653036 16535387753
49606163259 66141551012
66141551012 49606163
<5 bytes omitted>

用户输出 

4
16535387753 198424653036
66141551012 49606163259
49606163259 66141551012
198424653036 16535387753

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（39.in） 

87178876849 784609891641

答案文件（39.out） 

2
87178876849 784609891641
784609891641 87178876849

用户输出 

2
87178876849 784609891641
784609891641 87178876849

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（40.in） 

33540566239 402486794868

答案文件（40.out） 

4
33540566239 402486794868
402486794868 33540566239
100621698717 134162264956
134162264956 10062
<9 bytes omitted>

用户输出 

4
33540566239 402486794868
134162264956 100621698717
100621698717 134162264956
402486794868 33540566239

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（41.in） 

934952981837 626667315948

答案文件（41.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（42.in） 

550833610673 63126347766

答案文件（42.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（43.in） 

491010712635 775334560050

答案文件（43.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（44.in） 

85066201333 243783255919

答案文件（44.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（45.in） 

706783967254 186051920794

答案文件（45.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（46.in） 

422592811423 183442732736

答案文件（46.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（47.in） 

717362211998 720356771944

答案文件（47.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（48.in） 

552494136542 95622086211

答案文件（48.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（49.in） 

342877297536 2325603527

答案文件（49.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

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

输入文件（50.in） 

231501170516 751904909942

答案文件（50.out） 

0

用户输出 

0

Special Judge 信息 

Accepted!

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号