import java.io.*;
import java.util.*;
public class sirni {
static int n, max;
static int[] 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 int[n];
for (int i=0; i<n; i++){
int curr = file.nextInt();
arr[i] = curr;
max = Math.max(max, curr);
}
Arrays.sort(arr);
int prev = -1;
for (int i : arr){
if (i > prev){
findMultiples(i);
prev = 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){
int val = bs(base*k+1);
if (val != -1){
edges.add(new Edge(base, val, val % base));
}
}else{
int val = bs(base*k);
if (val != -1){
edges.add(new Edge(base, val, val % base));
}
}
k++;
}
}
public static int bs(int target){
int low = 0;
int high = n-1;
boolean found = false;
while (low < high){
int mid = (low + high)/2;
if (arr[mid] >= target){
found = true;
high = mid;
}else{
low = mid+1;
}
}
if (arr[low] < target){
return -1;
}
return arr[low];
}
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()); }
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
215 ms |
91012 KB |
Output is correct |
| 2 |
Correct |
1464 ms |
174708 KB |
Output is correct |
| 3 |
Correct |
339 ms |
92864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
11392 KB |
Output is correct |
| 2 |
Runtime error |
3281 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
91516 KB |
Output is correct |
| 2 |
Correct |
152 ms |
88340 KB |
Output is correct |
| 3 |
Correct |
243 ms |
92020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1136 ms |
68052 KB |
Output is correct |
| 2 |
Correct |
2476 ms |
198016 KB |
Output is correct |
| 3 |
Correct |
1995 ms |
105364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
809 ms |
34844 KB |
Output is correct |
| 2 |
Correct |
1942 ms |
124720 KB |
Output is correct |
| 3 |
Correct |
1377 ms |
64456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2025 ms |
129272 KB |
Output is correct |
| 2 |
Correct |
3229 ms |
252164 KB |
Output is correct |
| 3 |
Correct |
1520 ms |
98844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1227 ms |
38860 KB |
Output is correct |
| 2 |
Correct |
3267 ms |
252120 KB |
Output is correct |
| 3 |
Correct |
1862 ms |
105652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2375 ms |
138948 KB |
Output is correct |
| 2 |
Runtime error |
4319 ms |
786436 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1865 ms |
154116 KB |
Output is correct |
| 2 |
Runtime error |
4164 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
887 ms |
108316 KB |
Output is correct |
| 2 |
Runtime error |
4472 ms |
786432 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
