NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #214592 | #2809. 去发现新的最小公约吧 | Filberte | 100 | 23ms | 2052kb | C++11 | 794b | 2024-11-20 19:31:06 | 2024-11-20 23:03:01 |
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
int pri[100050], vis[100050], cnt;
int get_phi(int x){
int res = 1;
for(int i = 1;i <= cnt && pri[i] * pri[i] <= x;i++){
if(x % pri[i] == 0){
res *= pri[i] - 1;
x /= pri[i];
while(x % pri[i] == 0) x /= pri[i], res *= pri[i];
}
}
if(x > 1) res *= x - 1;
return res;
}
int32_t main(){
int maxn = 1e5 + 10;
for(int i = 2;i <= maxn;i++){
if(!vis[i]){
pri[++cnt] = i;
for(int j = i * i;j <= maxn;j += i)
vis[j] = 1;
}
}
int cas;cin >> cas;while(cas--){
int a, m;cin >> a >> m;
cout << get_phi(m / __gcd(a, m)) << endl;
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 1ms
memory: 2052kb
input:
100 8 4 6 2 5 2 5 1 4 4 3 6 2 2 7 8 8 7 10 7 4 2 6 6 1 10 10 4 10 5 4 1 7 4 1 2 8 6 1 7 1 4 7 4 3 10...
output:
1 1 1 1 1 1 1 4 6 6 1 1 4 1 1 1 2 1 2 6 2 2 4 6 1 1 6 2 1 2 2 1 6 4 1 4 1 2 2 2 4 1 1 4 1 2 6 2 6 2 ...
result:
ok 100 lines
Test #2:
score: 5
Accepted
time: 2ms
memory: 2048kb
input:
100 6 2 5 5 5 4 8 5 7 8 2 1 1 1 2 8 4 1 8 6 3 7 1 8 5 10 7 5 10 1 8 1 1 1 8 3 5 7 10 5 5 8 3 1 9 10 ...
output:
1 1 2 4 4 1 1 2 1 2 6 4 1 4 1 1 1 2 6 1 4 1 4 2 4 4 1 2 6 1 2 1 6 2 1 2 1 2 1 4 1 4 1 1 1 1 2 4 2 6 ...
result:
ok 100 lines
Test #3:
score: 5
Accepted
time: 0ms
memory: 2052kb
input:
100 236 591 570 152 211 246 425 284 417 411 226 543 288 381 897 378 20 532 711 277 34 734 70 255 750...
output:
392 2 80 140 136 360 126 36 108 276 366 32 8 360 480 156 160 200 18 12 264 180 946 700 36 28 40 260 ...
result:
ok 100 lines
Test #4:
score: 5
Accepted
time: 1ms
memory: 2052kb
input:
100 660 565 675 802 944 437 673 25 902 884 274 689 380 901 273 236 807 467 390 60 692 592 596 976 23...
output:
112 400 396 20 192 624 832 116 466 1 72 120 104 110 58 486 310 84 568 84 80 156 240 82 828 444 240 1...
result:
ok 100 lines
Test #5:
score: 5
Accepted
time: 1ms
memory: 2052kb
input:
100 854 59 565 564 467 216 670 462 138 150 907 217 249 167 539 865 530 621 670 837 329 443 122 228 6...
output:
58 184 72 120 20 180 166 688 396 540 442 36 96 28 148 128 84 42 660 400 2 352 132 156 24 192 880 52 ...
result:
ok 100 lines
Test #6:
score: 5
Accepted
time: 0ms
memory: 2048kb
input:
100 478 213 187 542 661 149 341 842 442 974 604 256 944 111 571 319 941 705 453 42 205 811 727 860 9...
output:
140 270 148 420 486 32 72 280 368 6 810 336 690 346 120 132 432 40 16 418 906 16 712 192 630 78 28 3...
result:
ok 100 lines
Test #7:
score: 5
Accepted
time: 1ms
memory: 2048kb
input:
100 2646495639 83073 7823694236 39102 881727324 40751 5863530312 76599 9543772391 54826 7121248446 9...
output:
27690 10584 40750 5672 26988 2300 18340 20736 91008 46656 5460 38304 41356 15624 29376 3044 29520 12...
result:
ok 100 lines
Test #8:
score: 5
Accepted
time: 1ms
memory: 2052kb
input:
100 806019626 27134 9014848910 45923 4669150950 62049 1308235830 62695 5818631975 39455 9158335197 7...
output:
13566 43488 18144 12538 606 25920 10656 692 976 10512 432 708 28152 10368 14160 1248 2008 37584 5280...
result:
ok 100 lines
Test #9:
score: 5
Accepted
time: 1ms
memory: 2052kb
input:
100 6554053173 22625 8911041785 51685 4277406929 90205 9387326879 63230 2818802968 71777 3597527462 ...
output:
18000 10336 72160 25288 71776 70840 8360 81438 42228 21060 9700 82 23052 10208 5880 7740 75768 9504 ...
result:
ok 100 lines
Test #10:
score: 5
Accepted
time: 1ms
memory: 2048kb
input:
100 6459050216 95926 2862928574 67445 6637029072 36117 7180652465 82640 7389019538 14217 9372556634 ...
output:
47962 44160 8024 8256 8112 28476 1680 184 91680 38840 22452 8176 24150 50112 38566 396 23688 726 880...
result:
ok 100 lines
Test #11:
score: 5
Accepted
time: 3ms
memory: 2048kb
input:
100 4045462519 6079203834 3592763471 4209040120 867154445 2049504817 3901368197 9681318674 579119579...
output:
1838452000 1679610240 2049504816 4840659336 3936988800 290668728 334972928 635791104 296681040 19876...
result:
ok 100 lines
Test #12:
score: 5
Accepted
time: 0ms
memory: 2048kb
input:
100 9123862244 9980053608 7985310706 2228386162 7603155722 8812166405 5630356584 4148773838 21142841...
output:
117036744 1061736480 6042628368 1885160760 186161484 15574716 2154381984 1451760720 4390921520 73304...
result:
ok 100 lines
Test #13:
score: 5
Accepted
time: 2ms
memory: 2048kb
input:
100 7426491555 2763484756 5457391985 6457160532 534914118 1572249269 2775997991 3809315223 888272698...
output:
1351638240 2029832448 1548782796 2082060288 862570548 8859492544 3089763600 540984288 9420766512 340...
result:
ok 100 lines
Test #14:
score: 5
Accepted
time: 0ms
memory: 2048kb
input:
100 9075853678 102993875 3010884417 2979594557 5930330168 4871508518 7600226984 8940737887 118514897...
output:
81259200 2979594556 2432911216 8921426976 766488800 1094959296 1766386800 4780323840 320288736 32923...
result:
ok 100 lines
Test #15:
score: 5
Accepted
time: 2ms
memory: 2052kb
input:
100 4021096645 5084700743 2505598974 4226942433 2028384176 2927433426 6560727784 4700774690 85539163...
output:
5084700742 1189168128 975811140 1880043120 1501398720 2622853120 4345506000 4710017280 2500801776 78...
result:
ok 100 lines
Test #16:
score: 5
Accepted
time: 0ms
memory: 2052kb
input:
100 5394932023 3200344581 8199663693 1374607804 3913573573 1880621978 4329635001 2811700871 25796777...
output:
1828768320 687121200 940178880 2408901120 537165432 3930587136 4972881152 2088039744 6420971520 1684...
result:
ok 100 lines
Test #17:
score: 5
Accepted
time: 2ms
memory: 2052kb
input:
100 4421181565 7950164025 7271383279 1281340308 6720617512 8240572244 5246156506 2633726799 44108925...
output:
841543040 424876480 2025225324 1506816000 4567127760 1220459298 488237026 4817552480 3011788800 7978...
result:
ok 100 lines
Test #18:
score: 5
Accepted
time: 2ms
memory: 2052kb
input:
100 64792226 2094307560 9263645727 6840282932 498184184 7131019629 1288538432 4944555527 6572306238 ...
output:
277689600 488443392 4740390576 4942705800 2825360928 786164256 944472672 729907200 9763287936 187931...
result:
ok 100 lines
Test #19:
score: 5
Accepted
time: 1ms
memory: 2048kb
input:
100 6673224472 4793077122 343436275 556644377 4195412270 4516001680 5415513582 589610523 3988294799 ...
output:
1597692372 556594896 225692208 194510592 3799984104 2110182480 6360951744 123869984 5499574380 13232...
result:
ok 100 lines
Test #20:
score: 5
Accepted
time: 2ms
memory: 2048kb
input:
100 4194270818 7289820928 7777260632 7890730149 3249835305 2579410381 3029031009 7280770225 70482421...
output:
1594644480 4812521472 2560582432 5823738320 4389534912 128653200 3138952872 1129075200 4383838272 19...
result:
ok 100 lines
