ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185234 | #2678. Small Multiple | wosile | 100 | 4635ms | 25332kb | C++ | 548b | 2023-09-26 09:19:35 | 2023-09-26 12:13:18 |
answer
#include<bits/stdc++.h>
using namespace std;
int dis[1000005],vis[1000005];
priority_queue<pair<int,int> >pq;
int main(){
int k,m;
scanf("%d%d",&k,&m);
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<m&&i<k;i++){
dis[i]=i;
pq.push(make_pair(-i,i));
}
while(!pq.empty()){
int f=pq.top().second;
pq.pop();
if(vis[f]==1)continue;
vis[f]=1;
for(int i=0;i<m;i++){
int v=(f*m+i)%k;
if(dis[v]>dis[f]+i){
dis[v]=dis[f]+i;
pq.push(make_pair(-dis[v],v));
}
}
}
printf("%d",dis[0]);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 5136kb
input:
32 4
output:
1
result:
ok single line: '1'
Test #2:
score: 5
Accepted
time: 0ms
memory: 5140kb
input:
25 6
output:
5
result:
ok single line: '5'
Test #3:
score: 5
Accepted
time: 0ms
memory: 5140kb
input:
19 3
output:
2
result:
ok single line: '2'
Test #4:
score: 5
Accepted
time: 0ms
memory: 5140kb
input:
64 7
output:
4
result:
ok single line: '4'
Test #5:
score: 5
Accepted
time: 0ms
memory: 5140kb
input:
86 10
output:
3
result:
ok single line: '3'
Test #6:
score: 5
Accepted
time: 0ms
memory: 5136kb
input:
17 2
output:
2
result:
ok single line: '2'
Test #7:
score: 5
Accepted
time: 492ms
memory: 16960kb
input:
937761 10
output:
6
result:
ok single line: '6'
Test #8:
score: 5
Accepted
time: 245ms
memory: 16416kb
input:
788944 8
output:
4
result:
ok single line: '4'
Test #9:
score: 5
Accepted
time: 175ms
memory: 11376kb
input:
573314 3
output:
4
result:
ok single line: '4'
Test #10:
score: 5
Accepted
time: 503ms
memory: 16400kb
input:
785883 5
output:
2
result:
ok single line: '2'
Test #11:
score: 5
Accepted
time: 450ms
memory: 16336kb
input:
769025 7
output:
6
result:
ok single line: '6'
Test #12:
score: 5
Accepted
time: 274ms
memory: 16884kb
input:
909894 4
output:
3
result:
ok single line: '3'
Test #13:
score: 5
Accepted
time: 164ms
memory: 15620kb
input:
585472 9
output:
8
result:
ok single line: '8'
Test #14:
score: 5
Accepted
time: 216ms
memory: 12244kb
input:
795020 5
output:
4
result:
ok single line: '4'
Test #15:
score: 5
Accepted
time: 222ms
memory: 15340kb
input:
514716 8
output:
3
result:
ok single line: '3'
Test #16:
score: 5
Accepted
time: 519ms
memory: 17180kb
input:
984458 5
output:
4
result:
ok single line: '4'
Test #17:
score: 5
Accepted
time: 160ms
memory: 9564kb
input:
645285 2
output:
4
result:
ok single line: '4'
Test #18:
score: 5
Accepted
time: 228ms
memory: 16048kb
input:
694328 9
output:
8
result:
ok single line: '8'
Test #19:
score: 5
Accepted
time: 340ms
memory: 16064kb
input:
698907 6
output:
2
result:
ok single line: '2'
Test #20:
score: 5
Accepted
time: 647ms
memory: 25332kb
input:
994036 7
output:
2
result:
ok single line: '2'