Bayan 2015 Contest Warm Up D. CGCDSSQ （math，pair，map，暴力）

哎，只能转题解了，，，

8165031	2014-10-10 15:53:42	njczy2010	D - CGCDSSQ	GNU C++	Accepted	156 ms	27584 KB
8163765	2014-10-10 13:03:56	njczy2010	D - CGCDSSQ	GNU C++	Time limit exceeded on test 10	2000 ms	32600 KB
8163761	2014-10-10 13:02:38	njczy2010	D - CGCDSSQ	GNU C++	Time limit exceeded on test 10	2000 ms	31600 KB
8163755	2014-10-10 13:01:12	njczy2010	D - CGCDSSQ	GNU C++	Wrong answer on test 9	46 ms	19700 KB
8163749	2014-10-10 12:59:54	njczy2010	D - CGCDSSQ	GNU C++	Wrong answer on test 9	31 ms	2100 KB

Given a sequence of integers a₁, ..., a_n and q queries x₁, ..., x_q on it. For each query x_i you have to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n and gcd(a_l, a_l + 1, ..., a_r) = x_i.

$\text{[math]}$ is a greatest common divisor of v₁, v₂, ..., v_n, that is equal to a largest positive integer that divides all v_i.

Input

The first line of the input contains integer n, (1 ≤ n ≤ 10⁵), denoting the length of the sequence. The next line contains n space separated integers a₁, ..., a_n, (1 ≤ a_i ≤ 10⁹).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 10⁵), denoting the number of queries. Then follows q lines, each contain an integer x_i, (1 ≤ x_i ≤ 10⁹).

Output

For each query print the result in a separate line.

Sample test(s)

Input

3 2 6 3 5 1 2 3 4 6

Output

1 2 2 0 1

Input

7 10 20 3 15 1000 60 16 10 1 2 3 4 5 6 10 20 60 1000

Output

14 0 2 2 2 0 2 2 1 1

题解以代码转自：http://blog.csdn.net/accelerator_/article/details/39892385

D：记录下gcd，每次多一个数字，就和前面的数字都取gcd，然后合并掉，下次利用这些已有的gcd去做，然后合并的过程要利用到gcd的递减性质，就可以直接从头往后找即可

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<queue>
  8 #include<map>
  9 #include<set>
 10 #include<string>
 11 //#include<pair>
 12 
 13 #define N 1000005
 14 #define M 1000005
 15 #define mod 1000000007
 16 //#define p 10000007
 17 #define mod2 100000000
 18 #define ll long long
 19 #define LL long long
 20 #define maxi(a,b) (a)>(b)? (a) : (b)
 21 #define mini(a,b) (a)<(b)? (a) : (b)
 22 
 23 using namespace std;
 24 
 25 int n,q;
 26 int a[N];
 27 map<int,ll>ans;
 28 typedef pair<int,ll>PP;
 29 PP save[N];
 30 int tot;
 31 
 32 int gcd(int x,int y)
 33 {
 34     if(y==0)
 35         return x;
 36     return gcd(y,x%y);
 37 }
 38 
 39 void ini()
 40 {
 41     int i;
 42     ans.clear();
 43     tot=0;
 44     for(i=1;i<=n;i++){
 45         scanf("%d",&a[i]);
 46     }
 47 }
 48 
 49 void solve()
 50 {
 51     int i,j;
 52     int sn;
 53     for(i=1;i<=n;i++){
 54         for(j=0;j<tot;j++){
 55             save[j].first=gcd(save[j].first,a[i]);
 56         }
 57         save[tot]=make_pair(a[i],1);
 58         tot++;
 59         sn=0;
 60         for(j=1;j<tot;j++){
 61             if(save[sn].first==save[j].first){
 62                 save[sn].second+=save[j].second;
 63             }
 64             else{
 65                 sn++;
 66                 save[sn]=save[j];
 67             }
 68         }
 69         sn++;
 70         tot=sn;
 71         for(j=0;j<tot;j++){
 72             ans[ save[j].first ]+=save[j].second;
 73         }
 74     }
 75 }
 76 
 77 void out()
 78 {
 79     int x;
 80     scanf("%d",&q);
 81     while(q--){
 82         scanf("%d",&x);
 83         printf("%I64d
",ans[x]);
 84     }
 85 }
 86 
 87 int main()
 88 {
 89     //freopen("data.in","r",stdin);
 90     //freopen("data.out","w",stdout);
 91    // scanf("%d",&T);
 92    // for(int ccnt=1;ccnt<=T;ccnt++)
 93    // while(T--)
 94     while(scanf("%d",&n)!=EOF)
 95     {
 96         //if(n==0 && k==0 ) break;
 97         //printf("Case %d: ",ccnt);
 98         ini();
 99         solve();
100         out();
101     }
102 
103     return 0;
104 }