Description
小H是個善于思考的學生，現在她又在思考一個有關序列的問題。
她的面前浮現出一個長度為n的序列{ai}，她想找出一段區間[L, R](1 <= L <= R <= n)。
這個特殊區間滿足，存在一個k(L <= k <= R)，并且對于任意的i(L <= i <= R)，ai都能被ak整除。這樣的一個特殊區間 [L, R]價值為R - L。
小H想知道序列中所有特殊區間的最大價值是多少，而有多少個這樣的區間呢？這些區間又分別是哪些呢？你能幫助她吧。

Input
第一行，一個整數n.
第二行，n個整數，代表ai.

Output
第一行兩個整數，num和val,表示價值最大的特殊區間的個數以及最大價值。
第二行num個整數，按升序輸出每個價值最大的特殊區間的L.

Sample Input
輸入1：
5
4 6 9 3 6
輸入2：
5
2 3 5 7 11

Sample Output
輸出1：
1 3
2
輸出2：
5 0
1 2 3 4 5

Data Constraint
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.

.
.
.
.
.
分析
水法真神奇，暴力出奇跡！

數據太水了，自己出的數據都能把程序卡到80分，結果交上去就AC了

我們暴力枚舉每一位為k
以當前位置向左、向右擴展，遇到不合法的就停止
最后判斷并統計答案即可

注意，可能會出現長度一樣，所在區間也一樣，這時就要判重(例如有多個數字為1的情況)
(但這種情況未得到有效的驗證，有可能只有1這種情況)

最后要將答案的數組排序輸出(以免出現數組不為有序的情況，同時，這種情況未得到有效的驗證)

所以你愛打不打

而真正的正解是這樣的：

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long ansl[500010],ansr[500010],a[500010]; int n;inline long long read() {int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w; }int main() {n=read();for (int i=1;i<=n;i++)a[i]=read();int num=0,val=0;for (int i=1;i<=n;i++){int l=i,r=i;while (a[r+1]%a[i]==0&&r<n) r++;while (a[l-1]%a[i]==0&&l>1) l--;if (r-l>val){val=r-l;num=0;num++;ansl[num]=l;ansr[num]=r;} elseif (r-l==val){if (ansl[num]!=l||ansr[num]!=r){num++;ansl[num]=l;ansr[num]=r;}}}sort(ansl+1,ansl+num+1);printf("%d %d\n",num,val);for (int i=1;i<=num;i++)printf("%lld ",ansl[i]);return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10458945.html

總結

以上是生活随笔為你收集整理的数字对的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。