import java.io.*;
import java.util.*;
public class sirni {
static int n, max;
static TreeSet<Integer> arr;
static ArrayList<Edge> edges = new ArrayList<>();
public static void main(String[] args) throws IOException{
FastIO file = new FastIO();
//BufferedReader file = new BufferedReader(new FileReader("file.in"));
//rintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Sirni.out")));
n = file.nextInt();
arr = new TreeSet<>();
for (int i=0; i<n; i++){
int curr = file.nextInt();
arr.add(curr);
max = Math.max(max, curr);
}
for (int i : arr){
findMultiples(i);
}
Collections.sort(edges);
DSU dsu = new DSU(max+1);
int ans = 0;
for (Edge curr : edges){
if (dsu.find(curr.from) != dsu.find(curr.to)){
dsu.union(curr.from, curr.to);
ans += curr.cost;
}
}
file.println(ans);
file.close();
}
public static void findMultiples(int base){
int k = 1;
while (base*k <= max){
if (k == 1){
if (arr.higher(base*k) != null){
int val = arr.higher(base*k);
edges.add(new Edge(base, val, val % base));
}
}else{
if (arr.ceiling(base*k) != null){
int val = arr.ceiling(base*k);
edges.add(new Edge(base, val, val % base));
}
}
k++;
}
}
static class Edge implements Comparable<Edge>{
int from, to, cost;
public Edge(int from ,int to, int cost){
this.from = from;
this.to = to;
this.cost = cost;
}
public int compareTo(Edge o){
return this.cost - o.cost;
}
}
static class Node implements Comparable<Node>{
int val;
int id;
public Node(int val ,int id){
this.val = val;
this.id = id;
}
public int compareTo(Node o){
if (this.val == o.val){
return this.id - o.id;
}
return this.val - o.val;
}
}
static class DSU{
int n;
int[] parent;
int[] size;
public DSU(int n){
this.n = n;
parent = new int[n];
size = new int[n];
for (int i=0; i<n; i++){
parent[i] = i;
size[i] = 1;
}
}
public int find(int a){
if (parent[a] == a){
return a;
}
return parent[a] = find(parent[a]); // Path compression
}
public void union(int a, int b){
a = find(a);
b = find(b);
if (a == b){
// Same component
return;
}
if (size[a] < size[b]){
// Point a to b
parent[a] = b;
size[b] += size[a];
}else{
// Point b to a
parent[b] = a;
size[a] += size[b];
}
}
}
static class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1<<16];
private int curChar, numChars;
// standard input
public FastIO() { this(System.in,System.out); }
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
// file input
public FastIO(String i, String o) throws IOException {
super(new FileWriter(o));
stream = new FileInputStream(i);
}
// throws InputMismatchException() if previously detected end of file
private int nextByte() {
if (numChars == -1) throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars == -1) return -1; // end of file
}
return buf[curChar++];
}
// to read in entire lines, replace c <= ' '
// with a function that checks whether c is a line break
public String next() {
int c; do { c = nextByte(); } while (c <= ' ');
StringBuilder res = new StringBuilder();
do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
return res.toString();
}
public int nextInt() { // nextLong() would be implemented similarly
int c; do { c = nextByte(); } while (c <= ' ');
int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10*res+c-'0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public double nextDouble() { return Double.parseDouble(next()); }
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
245 ms |
91576 KB |
Output is correct |
| 2 |
Correct |
1594 ms |
194988 KB |
Output is correct |
| 3 |
Correct |
374 ms |
93284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
181 ms |
11736 KB |
Output is correct |
| 2 |
Runtime error |
3653 ms |
786436 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
261 ms |
91944 KB |
Output is correct |
| 2 |
Correct |
167 ms |
88920 KB |
Output is correct |
| 3 |
Correct |
296 ms |
92700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1326 ms |
68700 KB |
Output is correct |
| 2 |
Correct |
3329 ms |
183708 KB |
Output is correct |
| 3 |
Correct |
1923 ms |
120032 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
547 ms |
26044 KB |
Output is correct |
| 2 |
Correct |
1950 ms |
116568 KB |
Output is correct |
| 3 |
Correct |
1234 ms |
63520 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2578 ms |
126256 KB |
Output is correct |
| 2 |
Correct |
4723 ms |
269224 KB |
Output is correct |
| 3 |
Correct |
1821 ms |
99816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
769 ms |
33628 KB |
Output is correct |
| 2 |
Correct |
4484 ms |
267184 KB |
Output is correct |
| 3 |
Correct |
1896 ms |
120472 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2127 ms |
134820 KB |
Output is correct |
| 2 |
Execution timed out |
5110 ms |
741620 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2048 ms |
151836 KB |
Output is correct |
| 2 |
Runtime error |
4961 ms |
786436 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
712 ms |
100584 KB |
Output is correct |
| 2 |
Execution timed out |
5092 ms |
649320 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
