Posted on 2010-08-04 22:18
MiYu 閱讀(860)
評論(2) 編輯 收藏 引用 所屬分類:
C/C++ 、
ACM ( 數(shù)論 )
//MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址 :
http://acm.hdu.edu.cn/showproblem.php?pid=2058
觀察a+1,a+2…a+d
全部相加等于M
即(a+1+a+d)*d/2 = M,
這里d是平方，我們可以從長度d入手，這樣就能把范圍由M轉(zhuǎn)換成M^1/2 ;
這里把代碼中的①和②解釋下：
①：當(dāng)a+1,a+2…a+3相加等于M時，即
(a+1+a+d)*d/2 = M
而a最小是0，所以(d+1)*d/2=M時d去最大值，就是這步把時間復(fù)雜度減小的。
d就是sqrt(2*M)
②：(a+1+a+d)*d/2 = M
所以a*d + (d+1)/2 = M
所以要使等式成立，M-(d+1)/2必須是d的倍數(shù)。
此為奮斗哥的代碼 : 0rz........下
//MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int N, M;
int main()
{
int flag = 0;
while(scanf("%d %d", &N, &M) && (M||N))
{
int i;
int len = int(sqrt(M*2.0)); // ①
for(i=len; i>=1; --i)
{
int temp = M-(i*i+i)/2; // ②
if(temp%i == 0)
printf("[%d,%d]\n", temp/i+1, temp/i+i);
}
printf("\n");
}
return 0;
}