結果

問題 No.1514 Squared Matching
ユーザー yassu0320yassu0320
提出日時 2022-06-05 02:46:08
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 3,207 bytes
コンパイル時間 116 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 410,596 KB
最終ジャッジ日時 2024-09-21 03:56:42
合計ジャッジ時間 6,027 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
20,120 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#!/usr/bin/env pypy3
from pprint import pprint
from string import ascii_lowercase as letter
from sys import setrecursionlimit, stdin
from typing import Dict, Iterable, Set
try:
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
except ModuleNotFoundError:
...
INF: int = (1 << 62) - 1
MOD1000000007 = 10**9 + 7
MOD998244353 = 998244353
setrecursionlimit(500_000)
readline = stdin.readline
input = lambda: stdin.readline().rstrip('\r\n')
def inputs(type_=int):
ins = input().split()
if isinstance(type_, Iterable):
return [t(x) for t, x in zip(type_, ins)]
else:
return list(map(type_, ins))
def input_(type_=int):
a, = inputs(type_)
return a
def input1() -> int:
return int(readline())
inputi = input1
def input2():
a = readline().split()
assert len(a) == 2
a[0] = int(a[0])
a[1] = int(a[1])
return a
def input3():
a = readline().split()
assert len(a) == 3
a[0] = int(a[0])
a[1] = int(a[1])
a[2] = int(a[2])
return a
def input4():
a = readline().split()
assert len(a) == 4
a[0] = int(a[0])
a[1] = int(a[1])
a[2] = int(a[2])
a[3] = int(a[3])
return a
yn = ['no', 'yes']
Yn = ['No', 'Yes']
YN = ['NO', 'YES']
# start coding
def isqrt(n):
"""
n.
: O(log(n)) (O(loglog(n))?)
Ref: http://www.ritsumei.ac.jp/se/~osaka/rejime/suuti/suuti2001.pdf
"""
x, y = n, (n + 1) // 2
while y < x:
x, y = y, (y + n // y) // 2
return x
def factor(n: int) -> Dict[int, int]:
if n < 2:
return dict()
res = dict()
for i in range(2, isqrt(n) + 1):
if n % i == 0:
res[i] = 0
while n % i == 0:
res[i] += 1
n //= i
if n != 1:
res[n] = 1
return res
class Osak:
def __init__(self, max_n: int) -> None:
self.max_n = max_n
self._create_table()
def _create_table(self):
"""
(max_n + 1)aa[k]kself.table.
: O(max_n * loglog(max_n))
"""
a = [None] * (self.max_n + 1)
for k in range(2, self.max_n + 1):
if a[k] is not None:
continue
for p in range(k, self.max_n + 1, k):
if a[p] is None:
a[p] = k
self.table = a
def is_prime(self, n: int) -> bool:
return n >= 2 and self.table[n] == n
def factor(self, n: int) -> dict:
assert 0 <= n < len(self.table)
if n <= 1:
return {}
d = {}
while n != 1:
k = self.table[n]
d[k] = 0
while n % k == 0:
d[k] += 1
n //= k
return d
def __str__(self) -> str:
return f'{self.__class__.__name__} <max_n: {self.max_n}>'
n = inputi()
osak = Osak(n)
res = 0
for i in range(1, n + 1):
d = factor(i)
t = 1
for p, c in d.items():
if c % 2 == 1:
t *= p
res += isqrt(n // t)
print(res)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0