結果
問題 | No.278 連続する整数の和(2) |
ユーザー |
![]() |
提出日時 | 2016-05-13 12:42:03 |
言語 | Python2 (2.7.18) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 911 bytes |
コンパイル時間 | 686 ms |
コンパイル使用メモリ | 7,040 KB |
実行使用メモリ | 51,280 KB |
最終ジャッジ日時 | 2024-11-14 12:55:14 |
合計ジャッジ時間 | 11,760 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 WA * 2 |
ソースコード
import mathN=int(raw_input())M=N*(N-1)/2upperBound = 2000001isPrime=[True for i in range((upperBound-3)/2+1)]for i in range((int(math.sqrt(upperBound-3))-3)/2+1): # k*k = (2i+3)^2 <= upperBound-3if isPrime[i]:k = i+i+3 # this is prime number# false out non_prime number from k*k# k*k = 4i^2+12i+9 = 2*(2i^2+6i+3)+3# k*(k+1) = 2*(2i^2+6i+3)+3 + 2i+3 ... even number. skip# k*(k+2) = 2*(2i^2+6i+3+k)+3non_prime = k*(i+1)+ifor j in range(non_prime,(upperBound-3)/2+1,k):isPrime[j]=Falseprimes = [2] + [i+i+3 for i in range((upperBound-3)/2+1) if isPrime[i]==True]#print len(primes)ans=1for p in primes:if min(N,M) <= 1:breaktmp=1while N%p==0 and M%p ==0:tmp*=ptmp+=1N/=pM/=pans*=tmpif min(N,M) > 1:p=min(N,M)if N%p==0 and M%p == 0:ans *= p+1print ans