shunfurh
编程介的小学生
2017-10-28 03:25

TrickGCD

  • bi
  • numbers
  • ai
  • gcd
  • each

Problem Description
You are given an array A , and Zhu wants to know there are how many different array B satisfy the following conditions?

  • 1≤Bi≤Ai
  • For each pair( l , r ) (1≤l≤r≤n) , gcd(bl,bl+1...br)≥2

Input
The first line is an integer T(1≤T≤10) describe the number of test cases.

Each test case begins with an integer number n describe the size of array A.

Then a line contains n numbers describe each element of A

You can assume that 1≤n,Ai≤105

Output
For the kth test case , first output "Case #k: " , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer mod 109+7

Sample Input
1
4
4 4 4 4

Sample Output
Case #1: 17

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答

为你推荐