NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #214411 | #2678. Small Multiple | meixuan | 100 | 7652ms | 168772kb | C++11 | 859b | 2024-11-18 20:31:55 | 2024-11-19 08:32:23 |
answer
#include<bits/stdc++.h>
using namespace std;
int dis[1000001];
vector<pair<int,int> >e[1000001];
struct node{
int u,v;
bool operator<(const node &a)const {
return v>a.v;
}
};
priority_queue<node> q;
bitset<1000001> vis;
int m,k;
void bfs(){
memset(dis,0x3f,sizeof dis);
for(int i=m;i>=1;i--){
dis[i%k]=i;
}
for(int i=1;i<=min(m,k-1);i++){
q.push(node{i,dis[i]});
// cout <<i<<' '<<dis[i]<<endl;
}
while(!q.empty()){
int now=q.top().u;
q.pop();
if(vis[now])continue;
vis[now]=1;
for(auto tv:e[now]){
if(dis[tv.first]>dis[now]+tv.second){
dis[tv.first]=dis[now]+tv.second;
q.push(node{tv.first,dis[tv.first]});
}
}
}
}
int main(){
cin >>k>>m;
for(int i=1;i<=k;i++){
for(int j=0;j<=m;j++){
e[i].push_back(make_pair((i*m+j)%k,j));
}
}
bfs();
cout <<dis[0]<<endl;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 7ms
memory: 28604kb
input:
32 4
output:
1
result:
ok single line: '1'
Test #2:
score: 5
Accepted
time: 12ms
memory: 28604kb
input:
25 6
output:
5
result:
ok single line: '5'
Test #3:
score: 5
Accepted
time: 3ms
memory: 28608kb
input:
19 3
output:
2
result:
ok single line: '2'
Test #4:
score: 5
Accepted
time: 12ms
memory: 28600kb
input:
64 7
output:
4
result:
ok single line: '4'
Test #5:
score: 5
Accepted
time: 8ms
memory: 28616kb
input:
86 10
output:
3
result:
ok single line: '3'
Test #6:
score: 5
Accepted
time: 9ms
memory: 28608kb
input:
17 2
output:
2
result:
ok single line: '2'
Test #7:
score: 5
Accepted
time: 730ms
memory: 168772kb
input:
937761 10
output:
6
result:
ok single line: '6'
Test #8:
score: 5
Accepted
time: 590ms
memory: 147832kb
input:
788944 8
output:
4
result:
ok single line: '4'
Test #9:
score: 5
Accepted
time: 319ms
memory: 59536kb
input:
573314 3
output:
4
result:
ok single line: '4'
Test #10:
score: 5
Accepted
time: 623ms
memory: 106400kb
input:
785883 5
output:
2
result:
ok single line: '2'
Test #11:
score: 5
Accepted
time: 602ms
memory: 96964kb
input:
769025 7
output:
6
result:
ok single line: '6'
Test #12:
score: 5
Accepted
time: 560ms
memory: 107984kb
input:
909894 4
output:
3
result:
ok single line: '3'
Test #13:
score: 5
Accepted
time: 424ms
memory: 119192kb
input:
585472 9
output:
8
result:
ok single line: '8'
Test #14:
score: 5
Accepted
time: 494ms
memory: 94804kb
input:
795020 5
output:
4
result:
ok single line: '4'
Test #15:
score: 5
Accepted
time: 400ms
memory: 109228kb
input:
514716 8
output:
3
result:
ok single line: '3'
Test #16:
score: 5
Accepted
time: 730ms
memory: 121932kb
input:
984458 5
output:
4
result:
ok single line: '4'
Test #17:
score: 5
Accepted
time: 382ms
memory: 62916kb
input:
645285 2
output:
4
result:
ok single line: '4'
Test #18:
score: 5
Accepted
time: 526ms
memory: 134516kb
input:
694328 9
output:
8
result:
ok single line: '8'
Test #19:
score: 5
Accepted
time: 457ms
memory: 91476kb
input:
698907 6
output:
2
result:
ok single line: '2'
Test #20:
score: 5
Accepted
time: 764ms
memory: 122680kb
input:
994036 7
output:
2
result:
ok single line: '2'
