QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100362#4229. GCD Harmonylgvc#WA 1859ms201572kbC++232.4kb2023-04-25 18:03:332023-04-25 18:03:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 18:03:37]
  • 评测
  • 测评结果：WA
  • 用时：1859ms
  • 内存：201572kb
查看
  • [2023-04-25 18:03:33]
  • 提交

answer

//这回只花了114514min就打完了。
//真好。记得多手造几组。
#include <bits/stdc++.h>
//#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define MOD 1000000007
#define eps 0.00000001
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
	if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
	*pp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pp-buf2,stdout);
	pp=buf2;
}
inline int read(void) {
	int w=1;
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9') {if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w*x;
}
void write(int x) {
	if(x<0) pc('-'),x=-x;
	static int sta[20];
	int top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while(x);
	while(top) pc(sta[--top]+48);
}
void we(int x) {
	write(x);
	pc('\n');
}
inline bool cmp_xi(int a,int b) {return a<b;}
inline bool cmp_da(int a,int b) {return a>b;}
int N,as,f[10009],a[50009],dp[5009][10009],nxt[10009],v[10009],hd[5009],to[10009],nxtt[10009],k;
inline void l(int u,int v) {nxtt[++k]=hd[u],to[k]=v,hd[u]=k;}
void conv(int n) {
	for(int i=2;i<=as;i++) {
		if(v[i]) continue;
		f[i]=INF;
		for(int j=i;j<=as;j+=i) {
			f[i]=std::min(f[i],dp[n][j]);
		}
	}
	for(int i=2;i<=as;i++) {
		int tp=i;
		dp[n][i]=INF;
		while(tp>1) {
			dp[n][i]=std::min(dp[n][i],f[nxt[tp]]);
			tp/=nxt[tp];
		}
	}
}
void dfs(int n,int f) {
	for(int j=2;j<=as;j++) if(j!=a[n]) dp[n][j]=j;
	for(int i=hd[n];i;i=nxtt[i]) {
		if(to[i]==f) continue;
		dfs(to[i],n);
		conv(to[i]);
		for(int j=2;j<=as;j++) {
			dp[n][j]+=dp[to[i]][j];
		}
	}
}
signed main(void) {
    //freopen("m.in","r",stdin);
    //freopen("m.out","w",stdout);
	N=read();
	as=2*N;
	for(int i=1;i<=N;i++) {
		a[i]=read();
		as=std::max(as,a[i]);
	} 
	for(int i=1;i<N;i++) {
		int u=read(),v=read();
		l(u,v),l(v,u);
	} 
	for(int i=1;i<=as;i++) nxt[i]=i;
	for(int i=2;i<=as;i++) for(int j=i*2;j<=as;j+=i) v[j]=1,nxt[j]=std::min(nxt[j],i);
	dfs(1,0);
	for(int i=2;i<=as;i++) as=std::min(as,dp[1][i]);
	printf("%d",as);
    return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5536kb

input:

6
5
6
3
4
9
12
1 2
1 3
1 4
1 6
3 5

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5464kb

input:

3
1
2
3
3 1
2 3

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 3ms
memory: 5864kb

input:

13
2
5
5
5
5
5
5
3
3
3
3
3
3
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13

output:

15

result:

ok single line: '15'

Test #4:

score: 0
Accepted
time: 2ms
memory: 5568kb

input:

9
2
5
5
5
5
3
3
3
3
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

output:

14

result:

ok single line: '14'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5796kb

input:

8
13
13
13
2
13
13
13
13
1 2
1 3
1 4
1 5
1 6
1 7
1 8

output:

13

result:

ok single line: '13'

Test #6:

score: 0
Accepted
time: 1767ms
memory: 199940kb

input:

5000
59
25
51
26
33
99
2
13
29
58
5
47
96
83
63
22
69
89
41
90
20
97
85
90
55
17
54
75
54
24
90
54
74
78
81
77
2
47
68
18
60
81
99
86
7
6
76
43
17
43
92
25
36
26
47
100
63
66
2
16
47
25
48
86
24
2
10
42
44
80
92
48
49
21
49
40
32
85
53
88
15
30
4
27
77
16
6
80
50
56
46
14
3
48
92
50
93
35
69
29
48
4...

output:

4778

result:

ok single line: '4778'

Test #7:

score: 0
Accepted
time: 1795ms
memory: 201088kb

input:

5000
15
8
34
68
69
24
72
65
85
5
11
7
24
50
94
98
99
88
99
31
58
93
94
14
92
17
45
61
85
83
66
97
35
52
33
41
98
10
77
59
33
23
21
49
83
93
23
77
60
49
27
2
73
10
31
23
8
73
3
94
19
74
78
82
86
95
14
18
58
15
5
58
99
60
82
34
82
6
96
31
70
6
8
49
82
51
95
52
95
55
94
21
74
83
19
7
99
74
49
65
25
6
5...

output:

4733

result:

ok single line: '4733'

Test #8:

score: 0
Accepted
time: 1798ms
memory: 200208kb

input:

5000
15
15
14
18
19
15
13
18
16
17
16
18
16
16
17
16
19
17
16
19
15
13
17
15
15
14
15
16
16
14
18
15
19
16
18
15
14
13
15
15
13
19
18
15
17
14
15
14
17
16
13
13
19
16
18
19
14
19
17
13
19
14
15
14
15
13
13
17
18
15
17
17
16
16
18
19
19
16
13
16
18
15
15
17
16
15
14
16
13
18
13
18
19
18
15
13
13
14
1...

output:

5609

result:

ok single line: '5609'

Test #9:

score: 0
Accepted
time: 1774ms
memory: 200928kb

input:

5000
97
96
97
94
96
94
95
95
95
93
95
94
96
96
95
94
93
95
95
97
95
96
94
97
97
97
94
95
93
96
94
94
96
93
93
93
97
94
96
95
94
94
94
97
94
96
93
97
95
97
93
96
93
93
95
97
96
93
94
97
95
94
94
95
96
97
93
94
97
96
97
93
93
93
97
94
94
95
95
95
94
96
95
93
96
97
97
95
94
93
97
93
97
96
94
94
93
93
9...

output:

5497

result:

ok single line: '5497'

Test #10:

score: 0
Accepted
time: 1792ms
memory: 200148kb

input:

5000
79
71
73
97
79
61
61
97
67
61
89
73
67
79
83
97
61
61
61
83
97
83
71
79
97
97
97
71
89
71
83
61
73
89
73
73
73
67
61
97
71
73
89
71
83
67
71
67
73
73
97
79
67
79
89
73
97
97
73
67
61
71
73
83
67
73
71
61
79
61
73
73
89
79
71
89
83
67
71
97
67
71
89
83
71
61
79
89
79
97
83
89
83
79
71
79
89
61
6...

output:

10000

result:

ok single line: '10000'

Test #11:

score: 0
Accepted
time: 1787ms
memory: 199704kb

input:

5000
73
83
73
97
97
73
97
83
83
83
73
83
73
97
97
73
83
73
83
97
97
83
97
73
97
83
97
73
97
73
97
97
83
97
97
83
73
83
97
83
83
73
83
97
73
73
97
83
83
83
97
73
97
97
83
83
97
73
73
97
73
73
97
83
83
97
73
97
83
83
73
97
73
97
73
73
73
73
97
83
97
83
97
73
83
97
83
83
73
73
83
73
83
97
83
83
97
97
8...

output:

10000

result:

ok single line: '10000'

Test #12:

score: 0
Accepted
time: 1807ms
memory: 200504kb

input:

5000
5
5
7
2
2
3
2
7
2
5
5
3
7
7
3
3
7
5
3
3
3
5
2
7
5
2
2
2
3
7
3
5
3
2
3
7
2
2
5
3
7
2
3
7
3
2
7
3
2
5
3
3
5
2
7
5
3
3
5
5
5
5
2
3
2
7
7
2
5
3
3
2
5
7
5
5
7
5
3
5
7
2
7
7
2
7
5
7
5
2
5
7
2
7
2
5
7
2
7
7
5
5
7
7
5
5
3
3
3
7
3
5
7
7
7
7
3
5
3
3
7
5
3
3
2
5
5
3
3
2
7
2
5
7
2
3
2
7
5
7
7
2
7
5
2
3
2
7...

output:

7404

result:

ok single line: '7404'

Test #13:

score: 0
Accepted
time: 1760ms
memory: 200072kb

input:

5000
71
71
71
71
73
71
71
73
73
71
73
73
73
73
73
73
73
73
71
73
71
71
73
73
71
71
73
71
71
71
73
71
71
71
73
73
73
73
71
71
73
71
71
71
71
71
71
73
71
71
71
71
71
73
71
71
71
71
71
73
71
73
73
73
73
73
73
71
71
73
73
71
73
71
71
71
71
71
71
73
73
73
73
71
71
73
73
73
73
71
71
71
73
71
71
71
71
71
7...

output:

10000

result:

ok single line: '10000'

Test #14:

score: 0
Accepted
time: 1783ms
memory: 199840kb

input:

5000
3
5
5
3
5
2
5
3
2
3
5
5
2
5
2
2
2
3
2
5
5
3
3
5
2
2
3
5
2
2
3
3
2
2
2
3
5
5
2
5
2
5
2
3
5
3
3
5
2
3
5
3
3
5
5
5
5
3
3
5
3
2
2
2
3
3
3
5
3
2
5
2
3
2
5
3
2
2
3
2
3
2
5
5
2
2
5
3
2
2
3
5
3
3
2
2
3
5
2
2
3
2
5
3
2
3
3
2
5
5
3
5
5
5
5
3
3
5
3
5
5
3
2
3
5
5
3
3
3
2
3
3
5
3
3
3
2
2
2
3
3
5
2
3
3
3
2
5...

output:

2126

result:

ok single line: '2126'

Test #15:

score: 0
Accepted
time: 1789ms
memory: 200172kb

input:

5000
26
17
19
19
11
19
17
11
26
17
19
17
26
19
11
19
17
11
26
26
11
26
11
11
19
11
17
17
26
19
17
11
26
17
17
11
17
19
11
17
11
26
11
17
11
26
19
17
11
17
19
26
11
19
26
26
17
11
19
17
11
17
17
17
11
26
26
17
19
11
11
19
17
26
19
19
17
19
11
17
11
11
19
17
11
11
11
26
11
17
19
17
26
11
26
17
19
11
1...

output:

5268

result:

ok single line: '5268'

Test #16:

score: 0
Accepted
time: 1859ms
memory: 200172kb

input:

5000
13
11
13
11
13
11
11
11
11
13
13
11
11
11
11
11
13
11
11
11
11
13
11
11
11
13
13
11
11
13
13
13
11
13
13
13
11
11
11
13
13
11
11
13
13
11
11
13
11
13
13
11
13
11
13
13
13
13
13
13
11
13
13
11
11
13
11
11
13
11
13
11
11
11
13
13
13
13
13
13
11
11
13
11
11
11
13
11
13
11
11
13
11
13
11
11
13
13
1...

output:

10000

result:

ok single line: '10000'

Test #17:

score: 0
Accepted
time: 1771ms
memory: 201260kb

input:

5000
3
2
5
5
2
2
5
2
2
3
2
3
2
2
2
5
5
5
2
2
5
2
5
2
3
3
3
2
3
2
5
2
3
2
5
2
3
2
5
2
5
3
5
5
5
3
2
5
5
3
2
2
3
5
3
5
2
2
2
2
5
5
5
2
5
2
2
5
2
2
3
2
3
2
2
5
2
5
2
3
3
3
5
5
3
5
3
2
5
5
3
3
2
3
2
2
2
3
2
3
2
3
2
2
2
5
2
5
5
2
2
3
3
2
3
2
2
5
2
2
3
5
3
3
5
2
2
5
5
3
2
3
3
3
3
5
3
3
5
3
5
2
3
2
3
2
3
2...

output:

6330

result:

ok single line: '6330'

Test #18:

score: 0
Accepted
time: 1773ms
memory: 200732kb

input:

5000
6
14
35
14
14
6
14
14
14
6
15
15
10
21
15
6
21
6
6
35
21
21
6
15
35
15
10
14
35
10
15
10
35
6
15
10
14
14
21
15
10
15
14
6
10
21
35
21
21
21
10
21
35
6
35
15
6
35
10
14
15
6
35
14
35
21
35
6
14
10
21
15
10
21
6
14
35
35
15
6
6
10
35
15
21
21
35
10
15
10
14
35
21
21
21
6
6
35
15
21
21
14
14
21
3...

output:

1666

result:

ok single line: '1666'

Test #19:

score: 0
Accepted
time: 1857ms
memory: 201188kb

input:

5000
21
15
6
10
6
14
6
14
10
15
10
14
10
15
35
15
14
14
6
6
10
35
21
14
10
35
10
15
10
6
15
14
15
10
21
21
21
15
35
21
21
6
15
21
6
35
10
10
10
15
10
15
15
10
21
15
35
10
6
15
21
35
15
35
15
35
14
15
10
6
35
10
14
10
14
6
21
10
21
35
10
35
21
14
10
15
10
6
10
35
6
14
6
35
15
21
14
15
35
21
10
35
21
...

output:

510

result:

ok single line: '510'

Test #20:

score: 0
Accepted
time: 1811ms
memory: 201336kb

input:

5000
5
1
1
1
1
5
1
3
1
1
3
1
1
1
3
3
1
1
1
1
3
1
3
1
1
1
5
3
5
1
3
1
1
1
3
3
1
1
5
1
1
1
5
5
3
5
1
1
1
1
5
1
1
1
5
5
1
1
1
1
1
3
3
1
5
1
5
1
1
3
3
1
1
3
1
3
1
1
1
1
1
1
1
3
1
5
3
3
3
1
3
1
1
5
1
1
1
1
3
3
3
5
5
5
5
3
1
5
5
5
1
3
1
1
1
1
1
5
3
1
3
1
3
3
1
3
3
1
1
5
3
3
3
3
3
5
1
1
1
3
1
1
5
1
1
5
3
1...

output:

9450

result:

ok single line: '9450'

Test #21:

score: 0
Accepted
time: 1793ms
memory: 201452kb

input:

5000
6
6
10
6
10
6
10
21
10
6
15
21
35
10
14
10
15
10
10
15
6
14
15
35
14
14
15
6
35
10
35
10
14
21
21
21
15
21
14
6
21
10
15
14
35
15
35
21
35
14
6
35
10
15
35
21
35
10
14
35
14
35
21
21
10
15
10
14
35
15
35
35
6
35
14
21
35
14
14
21
21
15
14
14
21
15
10
15
6
6
10
35
14
35
14
21
6
14
14
10
35
6
6
2...

output:

1965

result:

ok single line: '1965'

Test #22:

score: 0
Accepted
time: 1822ms
memory: 201572kb

input:

4999
100
94
98
90
94
86
90
86
81
94
80
80
98
89
90
92
97
93
91
89
94
85
92
82
84
82
93
80
99
92
91
84
98
90
95
86
94
89
82
85
84
97
83
98
94
94
83
100
91
97
84
95
94
93
93
90
84
90
96
82
89
97
83
85
83
95
82
90
92
90
83
85
100
93
84
86
86
94
89
94
88
100
88
97
89
98
96
95
95
97
85
95
87
95
84
99
80
...

output:

4469

result:

ok single line: '4469'

Test #23:

score: 0
Accepted
time: 1804ms
memory: 200728kb

input:

4999
75
75
62
65
78
63
61
62
68
68
72
69
79
63
77
74
79
78
79
70
75
68
69
78
80
63
68
76
70
62
63
67
69
80
78
71
71
77
76
67
62
74
69
67
69
67
62
78
67
62
71
65
64
68
76
61
76
80
67
63
70
62
64
67
63
65
65
64
71
77
68
66
60
63
73
72
75
77
64
76
63
78
68
80
63
78
68
71
65
80
70
66
73
75
62
67
75
67
7...

output:

4476

result:

ok single line: '4476'

Test #24:

score: 0
Accepted
time: 1779ms
memory: 201148kb

input:

4999
44
47
46
52
56
42
41
59
43
54
52
54
44
50
59
46
48
52
56
53
44
46
43
42
50
42
47
47
49
56
58
41
52
49
44
53
47
49
47
50
44
48
41
44
54
57
50
54
59
42
60
51
42
52
57
40
51
47
59
49
50
57
60
52
60
42
41
51
40
58
47
52
41
41
42
59
55
52
51
41
44
52
43
40
54
42
40
53
49
51
46
58
50
46
47
52
44
47
4...

output:

4641

result:

ok single line: '4641'

Test #25:

score: 0
Accepted
time: 1789ms
memory: 200700kb

input:

4999
29
32
28
31
33
21
26
21
40
29
21
28
23
26
21
31
32
31
22
30
35
38
24
31
35
25
35
40
25
22
37
40
22
36
39
33
28
37
23
32
27
28
27
20
29
38
40
40
31
20
31
30
22
34
20
26
39
26
28
39
35
36
31
40
25
21
39
23
24
29
35
35
31
24
29
40
23
27
26
21
27
37
25
25
35
40
32
33
26
30
28
37
29
28
24
20
34
21
3...

output:

4617

result:

ok single line: '4617'

Test #26:

score: 0
Accepted
time: 1799ms
memory: 200804kb

input:

5000
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7...

output:

0

result:

ok single line: '0'

Test #27:

score: -100
Wrong Answer
time: 1806ms
memory: 200728kb

input:

5000
55
35
77
35
35
35
77
35
35
55
77
35
77
77
35
77
55
35
77
35
77
55
55
35
77
77
77
35
55
55
35
77
35
55
55
55
55
77
55
35
77
77
35
35
77
35
55
35
35
55
77
35
55
35
35
55
55
55
35
55
55
35
35
77
55
35
55
77
55
35
55
55
55
77
77
77
35
35
77
35
35
35
35
35
77
55
35
35
55
55
35
77
55
35
55
35
77
55
3...

output:

7

result:

wrong answer 1st lines differ - expected: '0', found: '7'
English 繁體中文 简体中文

服务器时间: 2025-02-02 02:50:43 | 开源项目