TrickGCD
time limit per test 2.5 second memory limit per test 256 megabytes
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

传送门:HDU6053

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 1e9+7

Sample Input

1
2
3
1
4
4 4 4 4

Sample Output

1
Case #1: 17

题解

比赛时一直想用枚举素数gcd再容斥 但时间复杂度过不了 这题的要点有两点 第一个是对A[i]/gcd分块 想到这步后有两个做法 一个是筛法容斥nlogn 一个是提前求莫比乌斯函数 相反数就是每个数要乘的数(模拟容斥) 还有这道题Java有点卡时 需要把最小的那个数作为枚举gcd的终点 4900ms->2700ms 第一步 分块 统计每个数的倍数对答案的贡献 用前缀和维护 枚举倍数的操作是nlogn的 对于每个数的倍数 它有一个区间 可以用前缀和相减得到区间里的个数 第二步 筛法容斥 从后往前 筛倍数 这样保证每个数作为最高的gcd只被算了一次 或者巧用莫比乌斯: 根据容斥原理,ans = +[k=一个素数之积 时对答案的贡献] -[k=两个素数之积 时对答案的贡献] +[k=三个素数之积 时对答案的贡献] ... 故任意k对答案的贡献系数 μ(k) = 0 , k是完全平方数的倍数 = (-1)^(n-1) , k = p1×p2×p3×...×pn ,p是素数 μ(k) 是莫比乌斯函数的相反数 http://www.cnblogs.com/nicetomeetu/p/7248040.html 感觉讲的比较清楚的一篇博客
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.io.*;  
import java.util.*;
public class Main {
static long mod=(long) (1e9+7);
static int[]shu=new int[100050];
static int[]pre=new int[110500];
static long[]js=new long[100500];
static int[]prime=new int[100050];
static boolean[]notp=new boolean[100050];
static int[]mu=new int[100050];
public static void main(String[] args) throws IOException {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int q=0;
int t=sc.nextInt();
//makeMobius();
for(int k=1;k<=t;k++){
q++;
int n=sc.nextInt();
int min=(int) 1e6;
Arrays.fill(pre, 0);
pw.print("Case #"+q+": ");
for(int i=0;i<n;i++){
shu[i]=sc.nextInt();
min=Math.min(min, shu[i]);
pre[shu[i]]+=1;
}
for(int i=1;i<100050;i++){
pre[i]=pre[i-1]+pre[i];
}
for(int i=2;i<=min;i++){ //分块
js[i]=1;
for(int j=0;j<=100000;j+=i){
int sum=0;
int bs=j/i;
if(j+i-1>100000)sum=pre[100000]-pre[j-1];
else if(bs>=1) sum=pre[j+i-1]-pre[j-1];
else sum=pre[j+i-1];
if(bs==0&&sum>0)js[i]=0;
else js[i]=(js[i]*quickmod(j/i,sum))%mod;
}
}
for(int i=100000;i>=2;i--){ //nlogn筛倍数 第一种方法
for(int j=i+i;j<=100000;j+=i){
js[i]=(js[i]-js[j])%mod;
}
}
long res=0;
for(int i=0;i<=min;i++){
res=(res+js[i])%mod;
}
/*for(int i=0;i<=min;i++){ //巧用莫比乌斯 第二种方法
res=(res+js[i]*mu[i]*-1)%mod;
}*/
pw.println((res+mod)%mod);
pw.flush();
}

}
static long quickmod(long a,int n){
long res=1;
long result=1;
while(n>0){
if(n%2!=0)result=(result*a)%mod;
a=(a*a)%mod;
n=n/2;
}
return result;
}
static void makeMobius() {
Arrays.fill(notp, false);
mu[1] = 1;
int pnum=0;
for (int i = 2; i < 100010; i++) {
if (!notp[i]) {
prime[++pnum] = i; mu[i] = -1;
}
for (int j = 1; prime[j]*i < 100010; j++) {
notp[prime[j]*i] = true;
if (i%prime[j] == 0) {
mu[prime[j]*i] = 0;
break;
}
mu[prime[j]*i] = -mu[i];
}
}
}
}