首页 > 代码库 > GCD(st表)

GCD(st表)

2024-09-12 18:57:14   214人阅读

GCD

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3432    Accepted Submission(s): 1227


Problem Description

Give you a sequence of N(N≤100,000) integers : a1,...,an(0<ai≤1000,000,000). There are Q(Q≤100,000) queries. For each query l,r you have to calculate gcd(al,,al+1,...,ar) and count the number of pairs(l′,r′)(1≤l<r≤N)such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
 

 

Input

The first line of input contains a number T, which stands for the number of test cases you need to solve.

The first line of each case contains a number N, denoting the number of integers.

The second line contains N integers, a1,...,an(0<ai≤1000,000,000).

The third line contains a number Q, denoting the number of queries.

For the next Q lines, i-th line contains two number , stand for the li,ri, stand for the i-th queries.
 

 

Output

For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).

For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
 

 

Sample Input

1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4

Sample Output

Case #1:
1 8
2 4
2 4
6 1
 
 
题意:第一行T代表测试组数,第二行一个整数 N 代表长为 N 的序列，再一行是一个整数 Q ，代表有 Q 次询问，
然后 Q 行,每行两个整数 l,r 输出区间[l,r]的gcd 和有多少个区间 gcd 等于 gcd[l,r]
 
题解:想了很久，没想到好办法，后来发现RMQ这种问题，线段树还是不行的，如果离线的话，st表查询时间复杂度比线段树更小，为O(1)
st表学习:http://www.cnblogs.com/yangjiyuan/p/5493274.html
学了st表后，查询有多少区间gcd==gcd[l,r]还是不知道怎么搞，题解是,用二分离线预处理...
技术分享
 1 #include<iostream> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cstdio> 5 #include<map> 6 using namespace std; 7  8 #define LL long long 9 #define MAXN 10000510 11 int n;12 int num[MAXN];13 int mn[MAXN];14 int dp[MAXN][20];15 map<int,LL> res;16 17 int gcd(int a,int b)18 {   return b==0?a:gcd(b,a%b);}19 20 void Init()21 {22     mn[0]=-1;23     for (int i=1;i<=n;i++)24     {25         mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];26         dp[i][0]=num[i];27     }28     for (int j=1;j<=mn[n];j++)29         for (int i=1;i+(1<<j)-1<=n;i++)30         {31             dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);32         }33 }34 35 int st_calc(int l,int r)36 {37     int k = mn[r-l+1];38     return gcd(dp[l][k],dp[r-(1<<k)+1][k]);39 }40 41 void erfen()42 {43     res.clear();44     for (int i=1;i<=n;i++)  //以i为左起点的区间的所有公约数45     {46         int cur = i , gc = num[i];  //用二分求出47         while (cur <= n)48         {49             int l=cur,r=n;50             while(l<r)51             {52                 int mid = (l+r+1)>>1;53                 if (st_calc(i,mid)==gc) l=mid;54                 else r = mid -1;55             }56             if (res.count(gc)) res[gc]+=l-cur+1;57             else res[gc]=l-cur+1;58             cur = l + 1;59             if (cur<=n)60                 gc = gcd(gc,num[cur]);61         }62     }63 }64 65 int main()66 {67     int t;68     int cas=0;69     scanf("%d",&t);70     while (t--)71     {72         scanf("%d",&n);73         for (int i=1;i<=n;i++)74             scanf("%d",&num[i]);75         Init();76 77         erfen();78 79         int q;80         scanf("%d",&q);81         printf("Case #%d:\n",++cas);82         while (q--)83         {84             int x,y;85             scanf("%d%d",&x,&y);86             int kk = st_calc(x,y);87             printf("%d %lld\n",kk,res[kk]);88         }89     }90     return 0;91 }
View Code

 

 
 

GCD(st表)


联系
我们