數列

jzoj 2752

題目大意：

給你一個正整數n（有多組數據），讓你把它分為一個連續的正整數列之和（長度大于1），然你求著個數列最短的長度，如果這個序列不存在，那輸出-1

輸入樣例

9 2

輸出樣例

2 -1

數據范圍

對于所有數據，$n\le 26^3$。

解題思路

這道題我們要分類討論
我們先說奇數：
1很顯然是不可能的就是-1
大于1的整數可以分為$n/2$和$n/2+1$
然后是偶數：
我們又要 分類討論：
我們設這個序列是$a_1,a_2...a_{n?1},a_n,X,b_n,b_{n?1}...b_2,b_1$
X是中間數，那中間數$\times$長度等于輸入的N
如果序列長度是偶數
那X就是一個小數（x.5），且$b_n=a_n+1$
我們就把$a_1$和$b_1$，$a_n$和$b_n$分為一組，以此類推
那每一組都是奇數，就沒有偶數因子
我們把N分解質因子，奇數全放在每一組處，所有2放在長度
因為2不能放在每一組處，而如果把某些奇數放在長度處，那把2放在每一組處，就可以行成更短的奇數序列了，那就不可能是最優的
然后我們枚舉奇數的長度（具體實現看代碼）
每一次求出長度我們還要判斷有沒有小于等于0（就看中間數是否大于長度的一半，因為要從中間數往左一半的長度）

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n, m, i, ans; int main() {while(cin>>n){ans = -1;if (n > 1 && (n&1)) ans = 2;//奇數if (!(n&1))//偶數{m = n;while(!(m&1)) m >>= 1;//提取奇數因子總和if (m / 2 >= n / m) ans = n / m * 2;//每一組是m，判斷有沒有出界就用前一個數m/2（后一個數是m/2+1）//有n/m組，一組有兩個數，長度是n/m*2，那n/m就是長度一半i = 3;//枚舉奇數for (; i * i <= m && (ans == -1 || i < ans); i += 2)//要判斷是否枚舉的更優，且只枚舉到sqrt（m），因為如果大于sqrt（m）且有答案，那長度和中間數的奇數因子，掉反那會更優if (m % i == 0 && n / i >= (i + 1) / 2)//能整除，i是長度，中間數要把偶數因子也算進去，就是n/i，因為中間數也有一個長度，所以要加一ans = i;if (m != 1 && n / m >= (m + 1) / 2 && (ans == -1 || m < ans))//以m為長度的情況ans = m;}printf("%lld\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的【数学】数列（jzoj 2752）的全部內容，希望文章能夠幫你解決所遇到的問題。

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