ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185240 | #2678. Small Multiple | snow_trace | 100 | 3552ms | 61588kb | C++11 | 617b | 2023-09-26 09:44:09 | 2023-09-26 12:14:13 |
answer
#include<bits/stdc++.h>
using namespace std;
int x,b;
int dis[1000005];
vector<pair<int,int> >p[1000005];
int q[10000005];int l = 5000000,r = 4999999;
signed main(){
memset(dis,31,sizeof(dis));
cin >> x >> b;
for(int i = 0;i<x;i++){
p[i].push_back({i*b%x,0});
p[i].push_back({(i+1)%x,1});
}dis[1] = 1;q[++r] = 1;
while(l<=r){
int now = q[l];++l;
for(int i= 0;i<p[now].size();i++){
int to = p[now][i].first,c = p[now][i].second;
if(dis[to]>dis[now]+c){
dis[to] =dis[now]+c;
if(c == 0)q[--l] = to;
else q[++r] = to;
}
}
}cout << dis[0] << endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 8ms
memory: 28592kb
input:
32 4
output:
1
result:
ok single line: '1'
Test #2:
score: 5
Accepted
time: 3ms
memory: 28588kb
input:
25 6
output:
5
result:
ok single line: '5'
Test #3:
score: 5
Accepted
time: 11ms
memory: 28592kb
input:
19 3
output:
2
result:
ok single line: '2'
Test #4:
score: 5
Accepted
time: 3ms
memory: 28592kb
input:
64 7
output:
4
result:
ok single line: '4'
Test #5:
score: 5
Accepted
time: 7ms
memory: 28588kb
input:
86 10
output:
3
result:
ok single line: '3'
Test #6:
score: 5
Accepted
time: 12ms
memory: 28584kb
input:
17 2
output:
2
result:
ok single line: '2'
Test #7:
score: 5
Accepted
time: 294ms
memory: 60776kb
input:
937761 10
output:
6
result:
ok single line: '6'
Test #8:
score: 5
Accepted
time: 330ms
memory: 55936kb
input:
788944 8
output:
4
result:
ok single line: '4'
Test #9:
score: 5
Accepted
time: 163ms
memory: 47628kb
input:
573314 3
output:
4
result:
ok single line: '4'
Test #10:
score: 5
Accepted
time: 308ms
memory: 54680kb
input:
785883 5
output:
2
result:
ok single line: '2'
Test #11:
score: 5
Accepted
time: 214ms
memory: 54384kb
input:
769025 7
output:
6
result:
ok single line: '6'
Test #12:
score: 5
Accepted
time: 273ms
memory: 59392kb
input:
909894 4
output:
3
result:
ok single line: '3'
Test #13:
score: 5
Accepted
time: 205ms
memory: 48888kb
input:
585472 9
output:
8
result:
ok single line: '8'
Test #14:
score: 5
Accepted
time: 276ms
memory: 55916kb
input:
795020 5
output:
4
result:
ok single line: '4'
Test #15:
score: 5
Accepted
time: 180ms
memory: 46180kb
input:
514716 8
output:
3
result:
ok single line: '3'
Test #16:
score: 5
Accepted
time: 298ms
memory: 61276kb
input:
984458 5
output:
4
result:
ok single line: '4'
Test #17:
score: 5
Accepted
time: 176ms
memory: 49968kb
input:
645285 2
output:
4
result:
ok single line: '4'
Test #18:
score: 5
Accepted
time: 267ms
memory: 52656kb
input:
694328 9
output:
8
result:
ok single line: '8'
Test #19:
score: 5
Accepted
time: 236ms
memory: 52252kb
input:
698907 6
output:
2
result:
ok single line: '2'
Test #20:
score: 5
Accepted
time: 288ms
memory: 61588kb
input:
994036 7
output:
2
result:
ok single line: '2'