题目描述
饺子皮和橘子皮在搬砖。一共有 n 堆砖需要运走,第 i 堆有 ai 块。两个人比赛轮流搬砖,饺子皮先搬。
饺子皮首先会随便选择一堆砖搬走其中的 s1 块(至少搬一块);橘子皮会选择 s1 的倍数 s2(可以相等),然后从某一堆中搬走 s2 块;然后饺子皮会选择 s2 的倍数 s3,然后从某一堆中搬走 s3 块,以此类推。最先无法操作的人输。
饺子皮发现,在好多种情况下自己都能稳赢橘子皮。为了更好地向橘子皮展示自己的实力,饺子皮希望你帮他算一算有多少种开局方式能让饺子皮稳赢。两种开局方式不同,当且仅当饺子皮在第一轮搬走了不同堆中的砖,或者在同一堆砖中搬走了不同数量的砖。
输入格式
从标准输入读入数据。
输入的第一行一个整数 n 表示堆数;
第二行 n 个整数 ai 表示每一堆的砖数。
输出格式
输出到标准输出。
一行一个整数,表示能让饺子皮稳赢的开局方式数量。
样例
输入
1
5
输出
3
解释
如果使用 (x,y) 表示饺子皮第一次从第 x 堆中取走 y 块砖,那么能让饺子皮稳赢的开局方式有 (1,3),(1,4),(1,5)。
样例
输入
7
2 5 10 5 9 9 1
输出
13
样例三
见下载目录下的 ex_3.in 与 ex_3.ans。
数据范围
对于 50% 的数据,1≤n≤100,1≤ai≤100。
对于 100% 的数据,1≤n≤106,1≤ai≤106。
提示
输入量较大,请注意读入优化。