Problem Description

MDD随机生成了n(n<le5)个随机数x(x<=1e9),
这n个随机数排成一个序列,MDD有q(q<=le5)个询问,
每个询问给你一个a,问你这个序列中有多少个区间的最大公约数不为a

Input

第一行输入一个T,表示T组测试样例
每组样例包含一个n,表示n个随机数
再输入一个Q,表示Q个询问
每个询问输入一个a

Output

每个询问输出有多少个区间的gcd不为a

Sample Input

1
5
1 2 4 4 1
4
1
2
3
4

Sample Output

6
12
15
12

解法:听说还是暴力啊,卧槽

 #include <bits/stdc++.h>
#define int long long using namespace std; int nextInt(){
int d;
scanf("%lld",&d);
return d;
} map<int,int> mp;
int a[];
int b[]; int gcd(int a,int b){
if(a > b){
swap(a,b);
}
while(a > ){
int k = b % a;
b = a;
a = k;
}
return b;
} signed main(){
int T = nextInt();
while(T--){
mp.clear();
int n = nextInt();
for(int i = ; i < n ; i++){
a[i] = nextInt();
mp[a[i]]++;
}
for(int i = ; i < n ; i++){
for(int j = ; j < n - i - ; j++){
b[j] = gcd(a[j],a[j+]);
}
for(int j = ; j < n - i - ; j++){
a[j] = b[j];
mp[a[j]]++;
}
}
int q = nextInt();
while(q--){
int a = nextInt();
printf("%lld\n",n*(n+)/ - mp[a]);
}
}
return ;
}
05-12 09:33