UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185230#2678. Small Multipletkswls1007918ms130596kbC++111.2kb2023-09-26 09:13:052023-09-26 12:12:43

answer

#include<bits/stdc++.h>
using namespace std;
int n, m, head[1000005], nxt[20000007], to[20000007], w[20000007], ccnt, d[1000005], b[1000005], s, t;
inline void add(int p, int q, int ww) {
	nxt[++ccnt] = head[p];
	to[ccnt] = q;
	head[p] = ccnt;
	w[ccnt] = ww;
}
struct node {
	int name, num;
	bool operator<(const node& op)const {
		return num > op.num;
	}
};
void dijkstra() {
	for (int i = 1; i <= n; i++) {
		d[i] = (1 << 31) - 1;
	}
	s = 0;
	d[s] = 0;
	priority_queue<node> q;
	q.push(node{s, 0});
	memset(b, false, sizeof(b));
	while (q.size()) {
		node u = q.top();
		q.pop();
		if (b[u.name]) continue;
		b[u.name] = true;
		for (int i = head[u.name]; i; i = nxt[i]) {
			if (b[to[i]] == false && w[i] + d[u.name] < d[to[i]]) {
				d[to[i]] = w[i] + d[u.name];
				q.push(node{to[i], d[to[i]]});
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++) {
			add(i, ((i * m + j) % n) == 0 ? n : (i * m + j) % n, j);
		}
		if (i != 0) {
			add(i, ((i * m) % n) == 0 ? n : (i * m) % n, 0);
		}
	}
	dijkstra();
	cout << d[n];
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 5188kb

input:

32 4

output:

1

result:

ok single line: '1'

Test #2:

score: 5
Accepted
time: 0ms
memory: 5184kb

input:

25 6

output:

5

result:

ok single line: '5'

Test #3:

score: 5
Accepted
time: 0ms
memory: 5188kb

input:

19 3

output:

2

result:

ok single line: '2'

Test #4:

score: 5
Accepted
time: 0ms
memory: 5192kb

input:

64 7

output:

4

result:

ok single line: '4'

Test #5:

score: 5
Accepted
time: 0ms
memory: 5204kb

input:

86 10

output:

3

result:

ok single line: '3'

Test #6:

score: 5
Accepted
time: 0ms
memory: 5184kb

input:

17 2

output:

2

result:

ok single line: '2'

Test #7:

score: 5
Accepted
time: 745ms
memory: 130596kb

input:

937761 10

output:

6

result:

ok single line: '6'

Test #8:

score: 5
Accepted
time: 533ms
memory: 93508kb

input:

788944 8

output:

4

result:

ok single line: '4'

Test #9:

score: 5
Accepted
time: 371ms
memory: 33820kb

input:

573314 3

output:

4

result:

ok single line: '4'

Test #10:

score: 5
Accepted
time: 747ms
memory: 65568kb

input:

785883 5

output:

2

result:

ok single line: '2'

Test #11:

score: 5
Accepted
time: 654ms
memory: 82468kb

input:

769025 7

output:

6

result:

ok single line: '6'

Test #12:

score: 5
Accepted
time: 553ms
memory: 58944kb

input:

909894 4

output:

3

result:

ok single line: '3'

Test #13:

score: 5
Accepted
time: 426ms
memory: 79704kb

input:

585472 9

output:

8

result:

ok single line: '8'

Test #14:

score: 5
Accepted
time: 481ms
memory: 61980kb

input:

795020 5

output:

4

result:

ok single line: '4'

Test #15:

score: 5
Accepted
time: 388ms
memory: 65652kb

input:

514716 8

output:

3

result:

ok single line: '3'

Test #16:

score: 5
Accepted
time: 792ms
memory: 86876kb

input:

984458 5

output:

4

result:

ok single line: '4'

Test #17:

score: 5
Accepted
time: 341ms
memory: 27252kb

input:

645285 2

output:

4

result:

ok single line: '4'

Test #18:

score: 5
Accepted
time: 505ms
memory: 92032kb

input:

694328 9

output:

8

result:

ok single line: '8'

Test #19:

score: 5
Accepted
time: 500ms
memory: 67984kb

input:

698907 6

output:

2

result:

ok single line: '2'

Test #20:

score: 5
Accepted
time: 882ms
memory: 110804kb

input:

994036 7

output:

2

result:

ok single line: '2'