QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8637. 搬砖

Statistics

题目描述

饺子皮和橘子皮在搬砖。一共有 $n$ 堆砖需要运走,第 $i$ 堆有 $a_i$ 块。两个人比赛轮流搬砖,饺子皮先搬。

饺子皮首先会随便选择一堆砖搬走其中的 $s_1$ 块(至少搬一块);橘子皮会选择 $s_1$ 的倍数 $s_2$(可以相等),然后从某一堆中搬走 $s_2$ 块;然后饺子皮会选择 $s_2$ 的倍数 $s_3$,然后从某一堆中搬走 $s_3$ 块,以此类推。最先无法操作的人输。

饺子皮发现,在好多种情况下自己都能稳赢橘子皮。为了更好地向橘子皮展示自己的实力,饺子皮希望你帮他算一算有多少种开局方式能让饺子皮稳赢。两种开局方式不同,当且仅当饺子皮在第一轮搬走了不同堆中的砖,或者在同一堆砖中搬走了不同数量的砖。

输入格式

从标准输入读入数据。

输入的第一行一个整数 $n$ 表示堆数;

第二行 $n$ 个整数 $a_i$ 表示每一堆的砖数。

输出格式

输出到标准输出。

一行一个整数,表示能让饺子皮稳赢的开局方式数量。

样例

输入

1
5

输出

3

解释

如果使用 $(x,y)$ 表示饺子皮第一次从第 $x$ 堆中取走 $y$ 块砖,那么能让饺子皮稳赢的开局方式有 $(1,3),(1,4),(1,5)$。

样例

输入

7
2 5 10 5 9 9 1

输出

13

样例三

见下载目录下的 ex_3.inex_3.ans

数据范围

对于 $50\%$ 的数据,$1 \le n \le 100, 1 \le a_i \le 100$。

对于 $100\%$ 的数据,$1 \le n \le 10^6, 1 \le a_i \le 10^6$。

提示

输入量较大,请注意读入优化。