Responsive image

问题 1806 --TrickGCD

1806: TrickGCD

时间限制: 5 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

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

输入描述

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

输出描述

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

样例输入

1
4
4 4 4 4

样例输出

Case #1: 17

来源

 

[提交][状态]
ACM算法攻关部