QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]
Statistics

题目描述

饺子皮和橘子皮在搬砖。一共有 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.inex_3.ans

数据范围

对于 50% 的数据,1n100,1ai100

对于 100% 的数据,1n106,1ai106

提示

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