No.917 Make One With GCD
ningenMe
fineProblem Statement
You are given a sequence $A$ consisting of $N$ elements. The $i$-th ($1 \le i \le N$) element is $A_i$. Consider the non-empty subsequences of this sequence.
Here, a subsequence means "a sequence obtained by choosing and deleting $0$ or more elements of the sequence and arranging the remaining ones while keeping their original order".
Find the total number of subsequences of the sequence $A$ such that the greatest common divisor of all the elements they contain is $1$.
Note that two subsequences are treated as different if they contain different elements of the original sequence, even if all of their element values are the same.
Input
$N$
$A_{1}\ A_{2}\ \dots\ A_{N}$
All inputs are integers.
$1 \le N \le 50$
$1 \le A_i \le 10^8 (1 \le i \le N)$
Output
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 3
Output
5
The 5 subsequences {1},{1,2},{1,3},{2,3},{1,2,3} have a greatest common divisor of 1.
Sample 2
Input
4 1 1 1 1
Output
15
Note that two subsequences are treated as different if they contain different elements of the original sequence, even if all of their element values are the same.
Sample 3
Input
4 2 4 8 16
Output
0
No matter how a subsequence is chosen, its greatest common divisor is never 1.
Sample 4
Input
10 801754 703742 332182 68016 914814 8470 937255 293192 313080 501971
Output
763
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。