import java.io.*;
import java.util.*;
public class sirni {
static int n, max;
static TreeSet<Integer> arr;
static TreeSet<Edge> edges = new TreeSet<>();
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){
if (this.cost == o.cost){
if (this.to == o.to && this.from == o.from){
return 0;
}else{
return this.to - o.to;
}
}
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()); }
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
90808 KB |
Output is correct |
| 2 |
Incorrect |
1250 ms |
102940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
10564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
90520 KB |
Output is correct |
| 2 |
Correct |
184 ms |
89696 KB |
Output is correct |
| 3 |
Correct |
234 ms |
91840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2304 ms |
65936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
583 ms |
28640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4236 ms |
84188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
841 ms |
26944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3556 ms |
166032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3876 ms |
166632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
806 ms |
108976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
