-
-
Save tanzaku/60c6990ca94ab5b39ec567119ea9e184 to your computer and use it in GitHub Desktop.
Codeforces Round #428 (Div. 2) D. Winter is here
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.OutputStream; | |
import java.io.IOException; | |
import java.io.InputStream; | |
import java.io.PrintWriter; | |
import java.io.IOException; | |
import java.io.BufferedReader; | |
import java.io.Reader; | |
import java.io.InputStreamReader; | |
import java.io.InputStream; | |
/** | |
* Built using CHelper plug-in | |
* Actual solution is at the top | |
* | |
* @author tanzaku | |
*/ | |
public class Main { | |
public static void main(String[] args) { | |
InputStream inputStream = System.in; | |
OutputStream outputStream = System.out; | |
MyInput in = new MyInput(inputStream); | |
PrintWriter out = new PrintWriter(outputStream); | |
TaskD solver = new TaskD(); | |
solver.solve(1, in, out); | |
out.close(); | |
} | |
static class TaskD { | |
static final int mod = (int) 1e9 + 7; | |
public void solve(int testNumber, MyInput in, PrintWriter out) { | |
final int MAX = 1000000 + 1; | |
int[] c = new int[MAX]; | |
int n = in.nextInt(); | |
for (int i = 0; i < n; i++) { | |
int a = in.nextInt(); | |
c[a]++; | |
} | |
for (int i = 1; i < MAX; i++) { | |
for (int j = i * 2; j < MAX; j += i) { | |
c[i] += c[j]; | |
} | |
} | |
// c[i] : iの倍数の数 | |
int[] pow = new int[MAX]; | |
pow[0] = 1; | |
for (int i = 1; i < pow.length; i++) pow[i] = (int) (pow[i - 1] * 2L % mod); | |
long ans = 0; | |
long[] dp = new long[MAX]; | |
for (int i = MAX - 1; i > 1; i--) | |
if (c[i] > 0) { | |
dp[i] = pow[c[i] - 1] * (long) c[i] % mod; | |
for (int j = i * 2; j < MAX; j += i) { | |
dp[i] -= dp[j]; | |
} | |
ans += dp[i] * i % mod; | |
} | |
out.println((ans % mod + mod) % mod); | |
} | |
} | |
static class MyInput { | |
private final BufferedReader in; | |
private static int pos; | |
private static int readLen; | |
private static final char[] buffer = new char[1024 * 8]; | |
private static char[] str = new char[500 * 8 * 2]; | |
private static boolean[] isDigit = new boolean[256]; | |
private static boolean[] isSpace = new boolean[256]; | |
private static boolean[] isLineSep = new boolean[256]; | |
static { | |
for (int i = 0; i < 10; i++) { | |
isDigit['0' + i] = true; | |
} | |
isDigit['-'] = true; | |
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true; | |
isLineSep['\r'] = isLineSep['\n'] = true; | |
} | |
public MyInput(InputStream is) { | |
in = new BufferedReader(new InputStreamReader(is)); | |
} | |
public int read() { | |
if (pos >= readLen) { | |
pos = 0; | |
try { | |
readLen = in.read(buffer); | |
} catch (IOException e) { | |
throw new RuntimeException(); | |
} | |
if (readLen <= 0) { | |
throw new MyInput.EndOfFileRuntimeException(); | |
} | |
} | |
return buffer[pos++]; | |
} | |
public int nextInt() { | |
int len = 0; | |
str[len++] = nextChar(); | |
len = reads(len, isSpace); | |
int i = 0; | |
int ret = 0; | |
if (str[0] == '-') { | |
i = 1; | |
} | |
for (; i < len; i++) ret = ret * 10 + str[i] - '0'; | |
if (str[0] == '-') { | |
ret = -ret; | |
} | |
return ret; | |
} | |
public char nextChar() { | |
while (true) { | |
final int c = read(); | |
if (!isSpace[c]) { | |
return (char) c; | |
} | |
} | |
} | |
int reads(int len, boolean[] accept) { | |
try { | |
while (true) { | |
final int c = read(); | |
if (accept[c]) { | |
break; | |
} | |
if (str.length == len) { | |
char[] rep = new char[str.length * 3 / 2]; | |
System.arraycopy(str, 0, rep, 0, str.length); | |
str = rep; | |
} | |
str[len++] = (char) c; | |
} | |
} catch (MyInput.EndOfFileRuntimeException e) { | |
} | |
return len; | |
} | |
static class EndOfFileRuntimeException extends RuntimeException { | |
} | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment