d756. 10290 - {Sum+=i++} to Reach N
標籤 :
通過比率 : 51人/169人 ( 30% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-09-23 20:30

內容
所有的正整數都可以以連續的正整數相加的和來表達。例如:9可以有3種方式:2+3+4,4+5,9。給你一個整數N,請你算出有多少種N以連續的非負整數相加的和來表達的方式。
輸入說明
每筆測試資料一列。每列有1個整數 N(0 <= N <= 9*1014)。
輸出說明
對每一列輸入,請輸出有多少種N以連續的非負整數相加的和來表達的方式。
範例輸入 #1
9
11
12
範例輸出 #1
3
2
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (80%): 3.0s , <1M
公開 測資點#1 (20%): 3.0s , <1M
提示 :

有仔細看到題目的名子的人,就可以跟我code出一樣的程式碼。(如下,最大複雜度:O(n^2))

  1. #include 
  2. using namespace std ;
  3. int main ()
  4. {
  5.     long long n , ans , i , j , sum ;
  6.     while ( cin >> n )
  7.     {
  8.         ans = 0 ;
  9.         for ( i = 0 ; i <= n ; i ++ )
  10.         {
  11.             sum = 0 ;
  12.             for ( j = i ; sum < n ; j ++ )
  13.             {
  14.                 sum += j ;
  15.             }
  16.             if ( sum == n )
  17.             {
  18.                 ans ++ ;
  19.             }
  20.         }
  21.         cout << ans << '\n' ;
  22.     }
  23. }

 最大複雜度:O(n^0.5)在uva是會Time limit exceeded的。

※Luckycat譯(翻譯有誤,UVa Online Judge上寫的是連續整數合)

※感謝morris1028提供測資。(好多人WA.....)

※感謝liouzhou_101幫忙修改題目敘述。

※感謝liouzhou_101幫忙增加第二筆測試資料的第701~706行。此外,如果拿到NA80分的表示UVa可能已經AC,如果想要拿到滿分請把質數表建大一點。

標籤:
出處:
UVa10290

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」