|
Темы:
Games and winning strategies
Masha and Dasha play a game with N (\(1<=N<=10^5\)) piles of pebbles, where The ith pile contains ai pebbles (\(1<=i< =N\), \(1<=a_i<=10^6\)). They take turns walking, Masha goes first.
- First Masha chooses some positive number
s1 and removes s1 pebbles from some pile containing at least s1 pebbles.
- Then Dasha chooses some positive number
s2 such that s2 divides into s1 and removes s2 pebbles from some pile containing at least s2 pebbles.
- Then Masha chooses some positive number
s3, which is divisible by s2 and removes s3 pebbles from some pile that contains at least s3 pebbles.< /li>
- In the general case
si, the number of pebbles that are removed on the move i must be a divisor of s< sub>i+1.
The one who cannot make a move loses.
Calculate the number of ways Masha can remove the pebbles on her first move in order to guarantee her victory (that is, there is a strategy that Masha will use to win regardless of Dasha's moves). Two methods of removing pebbles are said to be different if they remove a different number of pebbles or they remove pebbles from different piles.
Input
The first line contains N.
The second line contains N single-space separated integers a1,…,aN.
Imprint
Print the number of ways Masha can remove the stones on her first move to guarantee herself a win.
For calculations use the 64th integer e.g. "long long" in C/C++.
Examples
| # |
Input |
Output |
Note |
| 1 |
1
7 |
4 |
Masha chooses 4, 5, 6, 7 pebbles from one pile and the game will end immediately. |
| 2 |
6
3 2 3 2 3 1
| 8 |
Masha wins if she removes 2 or 3 pebbles from any pile. Then the players will take turns taking the same number of pebbles, but Masha will make the last move. |
|