D. Pair of Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Simon has an arraya1,a2,…,an, consisting ofnpositive integers. Today Simon asked you to find a pair of integersl,r(1≤l≤r≤n), such that the following conditions hold:
there is integerj(l≤j≤r), such that all integersal,al+1,…,arare divisible byaj;valuer-ltakes the maximum value among all pairs for which condition1is true;
Help Simon, find the required pair of numbers(l,r). If there are multiple required pairs find all of them.
Input
The first line contains integern(1≤n≤3·105).
The second line containsnspace-separated integersa1,a2,…,an(1≤ai≤106).
Output
Print two integers in the first line — the number of required pairs and the maximum value ofr-l. On the following line print alllvalues from optimal pairs in increasing order.
Sample test(s)
input
54 6 9 3 6
output
1 32
input
51 3 5 7 9
output
1 41
input
52 3 5 7 11
output
5 01 2 3 4 5
Note
In the first sample the pair of numbers is right, as numbers6,9,3are divisible by3.
In the second sample all numbers are divisible by number1.
In the third sample all numbers are prime, so conditions1and2are true only for pairs of numbers(1,1),(2,2),(3,3),(4,4),(5,5).
恶心的题：需要注意去重
题意：一个区间l,r,纯在一个x (l<=x<=r)使得整个区间的数都可以整除a[x]),求r-l最大的情况，如有多组，按l小的输出
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)#define pii pair<int,int>#define eps 1e-8#define fre(i,a,b) for(i = a; i < b; i++)#define free(i,b,a) for(i = b; i >= a;i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define ssf(n)scanf("%s", n)#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define bugpf("Hi\n")using namespace std;#define INF 0x3f3f3f3f#define N 1000000vector<pii>ans;int a[N],le[N],ri[N];int vis[N];int n;int main(){int i,j;while(~sf(n)){fre(i,1,n+1)sf(a[i]);for(i=1;i<=n;i++){le[i]=i;while(le[i]>1&&a[le[i]-1]%a[i]==0)le[i]=le[le[i]-1];}for(i=n;i>=1;i–){ri[i]=i;while(ri[i]<n&&a[ri[i]+1]%a[i]==0)ri[i]=ri[ri[i]+1];}ans.clear();for(i=1;i<=n;i++){int temp=ri[i]-le[i];if(ans.size()==0){ans.push_back(make_pair(le[i],ri[i]-le[i]));continue;}if(temp>ans[0].second){ans.clear();ans.push_back(make_pair(le[i],ri[i]-le[i]));continue;}if(temp==ans[0].second){ans.push_back(make_pair(le[i],ri[i]-le[i]));}}int all=0;int pre=-1;for(i=0;i<ans.size();i++)if(ans[i].first!=pre){all++;pre=ans[i].first;}pf("%d %d\n",all,ans[0].second);pre=-1;int i=0;for(i=0;i<ans.size();i++) {if(ans[i].first==pre) continue; //防止有多个数相同，，那么区间都是一个，需要去重pre=ans[i].first;if(i) pf(" ");pf("%d",pre); }pf("\n");} return 0;}
人生不如意十之八-九，与其诅咒黑暗，倒不如在生命中点燃一盏灯
