﻿ Fuzhou University OnlineJudge ﻿
Problem 2106 How many tuples

## Problem Description

Given m positive integer a[1],a[2]…a[m]. We run the following program (in C++):

const int MAXN = 20; int a[MAXN], m; int gcd(int a, int b) {return b ? gcd(b, a % b) : a;} long long cnt = 0; void gao(int cur, int g) { if (cur > m) { if (g == 1)++cnt; return; } for (int i = 1; i <= a[cur]; ++i) gao(cur + 1, g < 0 ? i : gcd(g, i)); } int main() { scanf("%d", &m); for (int i = 1; i <= m; ++i) scanf("%d", a + i); gao(1, -1); cout << cnt << endl; return 0; }

Here gcd is the Greatest Common Divisor, Obviously, the program above is to find the number of tuples (b[1], b[2], …, b[m]) such that:

(1) gcd(b[1], b[2], …, b[m])=1. (Here we define gcd(num)=num, that is: gcd(9)=9, gcd(2)=2)

(2) 1≤b[i]≤a[i]. (1≤i≤m, b[i] is an integer)

Now in this problem, the m and a[i] may be very large! So could you write one efficient program to find the answer? The answer may be too large. So you can just output the answer Mod 1,000,000,007.

## Input

The first line of the input contains an integer T (T≤10,000), indicating the number of test cases.

Then T cases, for any case, only two lines.

The first line is one integer m(1≤m≤20).

The second line has m integers indicate a[1], a[2], …, a[m] (1≤a[i]≤100,000,000, 1≤i≤m).

The answer may be too large. So you can just output the answer Mod 1,000,000,007.

## Output

For each test case, print a line containing the answer Mod 1,000,000,007.

## Sample Input

3 2 5 5 2 10000 9873 2 1234 5678

## Sample Output

19 60026156 4261566

## Hint

In the first case, we have 5*5=25 tuples: (1, 1), (1, 2), …, (5, 3), (5, 4), (5, 5). Only 19 of them have the gcd 1. This problem is not very easy, and you have to make sure that you find one efficient algorithm.

## Source

“高教社杯”第三届福建省大学生程序设计竞赛

Submit  Back  Status  Discuss
﻿