vijos-P 1302連続自然数和(式導出+python)

P 302連続自然数和
Accepted
ラベル:[ラベルを表示]
説明
1つの与えられた自然数Mに対して、すべての連続する自然数セグメント(連続個数が1より大きい)を求め、これらの連続する自然数セグメントのすべての数の和はMである.
例:1998+1999+2000+2001+2002=10000であるため、1998から2002までの自然数セグメントはM=10000の解である.
書式設定
入力フォーマット
1つの整数を含む個々の行はMの値を与える(10<=M<=200000)
出力フォーマット
各行の2つの自然数は、条件を満たす連続自然数セグメントの最初の数と最後の数を与え、2つの数の間に1つのスペースで隔てられ、すべての出力行の最初の数は小さいから大きいまで昇順に並べられ、与えられた入力データに対して、少なくとも1つの解が保証される.
サンプル1
サンプル入力1[コピー]

10000

サンプル出力1[コピー]

18 142 
297 328 
388 412 
1998 2002

       C++      ，      ，    ，                   ，                     ，                       ，            ，  ，      ，     python  ，  c++46ms     ，      python       ， c++    0ms。

 
       
                             
  
m = math.sqrt(float(2 * n) + pow(a * 0.5,2.0)) - a * 0.5
  
if m == int(m):
        print i + 1,i + int(m)
  
     ，   ，           ，            
  
        ，         ：
  
 
       
        ：
  
         ：(2a + m)(m + 1) = 2n -> 2a(m + 1) = 2n - m(m + 1) - > 2a = 2n / (k + 1) - m
  
   a     ，2n % (k + 1)        ，   (2n / (k + 1) - m) % 2        
  
                ，           ，          
  
         
  
    pythonAC  ：
  
 
       
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
n = int(raw_input())
cnt = int(math.sqrt(2 * n))
i = cnt
while cnt > 0:
    if not ((2 * n) % (cnt + 1)):
        m = 2 * n / (cnt + 1)
        m -= cnt
        m >>= 1
        if (2 * m + cnt) * (cnt + 1) / 2 == n and m >= 0:
            print m,m + cnt
    cnt -= 1
            
  
 
  
制限