NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #214641 | #2809. 去发现新的最小公约吧 | Invisible_H | 50 | 683ms | 1192kb | C++ | 3.1kb | 2024-11-20 21:44:21 | 2024-11-20 23:09:33 |
answer
#include <bits/stdc++.h>
using namespace std;
const long long INF=1e18;
long long gcd(long long a,long long b){
long long az=__builtin_ctzl(a),bz=__builtin_ctzl(b);
long long z=min(az,bz),dif;
b>>=bz;
while(a){
a>>=az,dif=b-a;
az=__builtin_ctzl(dif);
b=min(a,b),a=abs(dif);
}
return b<<z;
}
void solve(){
long long a,m;scanf("%lld%lld",&a,&m);
long long gc=gcd(a,m),sum=0;
for(long long x=0;x<m;x+=gc){
sum+=(gcd(a+x,m)==gc);
}
printf("%lld\n",sum);
}
signed main(){
long long T;scanf("%lld",&T);
while(T--){
solve();
}
return 0;
}
/*
CCCCCCCCCCCCC AAA IIIIIIIIII CCCCCCCCCCCCC AAA IIIIIIIIII AAA
CCC::::::::::::C A:::A I::::::::I CCC::::::::::::C A:::A I::::::::I A:::A
CC:::::::::::::::C A:::::A I::::::::I CC:::::::::::::::C A:::::A I::::::::I A:::::A
C:::::CCCCCCCC::::C A:::::::A II::::::IIC:::::CCCCCCCC::::C A:::::::A II::::::II A:::::::A
C:::::C CCCCCC A:::::::::A I::::I C:::::C CCCCCC A:::::::::A I::::I A:::::::::A
C:::::C A:::::A:::::A I::::IC:::::C A:::::A:::::A I::::I A:::::A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::AAAAAAAAA:::::A I::::IC:::::C A:::::AAAAAAAAA:::::A I::::I A:::::AAAAAAAAA:::::A
C:::::C A:::::::::::::::::::::A I::::IC:::::C A:::::::::::::::::::::A I::::I A:::::::::::::::::::::A
C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I A:::::AAAAAAAAAAAAA:::::A
C:::::CCCCCCCC::::C A:::::A A:::::A II::::::IIC:::::CCCCCCCC::::C A:::::A A:::::A II::::::II A:::::A A:::::A
CC:::::::::::::::C A:::::A A:::::A I::::::::I CC:::::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCC::::::::::::C A:::::A A:::::A I::::::::I CCC::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIII CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIIIAAAAAAA AAAAAAA
*/
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 1188kb
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: 0ms
memory: 1188kb
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: 1188kb
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: 1188kb
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: 1192kb
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: 1ms
memory: 1192kb
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: 181ms
memory: 1188kb
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: 160ms
memory: 1192kb
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: 171ms
memory: 1192kb
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: 168ms
memory: 1192kb
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: 0
Time Limit Exceeded
input:
100 4045462519 6079203834 3592763471 4209040120 867154445 2049504817 3901368197 9681318674 579119579...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
100 9123862244 9980053608 7985310706 2228386162 7603155722 8812166405 5630356584 4148773838 21142841...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
100 7426491555 2763484756 5457391985 6457160532 534914118 1572249269 2775997991 3809315223 888272698...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
100 9075853678 102993875 3010884417 2979594557 5930330168 4871508518 7600226984 8940737887 118514897...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
100 4021096645 5084700743 2505598974 4226942433 2028384176 2927433426 6560727784 4700774690 85539163...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
100 5394932023 3200344581 8199663693 1374607804 3913573573 1880621978 4329635001 2811700871 25796777...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
100 4421181565 7950164025 7271383279 1281340308 6720617512 8240572244 5246156506 2633726799 44108925...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
100 64792226 2094307560 9263645727 6840282932 498184184 7131019629 1288538432 4944555527 6572306238 ...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
100 6673224472 4793077122 343436275 556644377 4195412270 4516001680 5415513582 589610523 3988294799 ...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
100 4194270818 7289820928 7777260632 7890730149 3249835305 2579410381 3029031009 7280770225 70482421...
