結果
問題 | No.1243 約数加算 |
ユーザー |
|
提出日時 | 2021-07-09 03:36:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 3,063 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 71,552 KB |
最終ジャッジ日時 | 2024-07-01 13:51:59 |
合計ジャッジ時間 | 1,435 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 |
ソースコード
import sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import gcd,loginput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())def isPrimeMR(n):if n==1:return 0d = n - 1d = d // (d & -d)L = [2, 3, 5, 7, 11, 13, 17]if n in L:return Truefor a in L:t = dy = pow(a, t, n)if y == 1: continuewhile y != n - 1:y = (y * y) % nif y == 1 or t == n - 1: return 0t <<= 1return 1def findFactorRho(n):from math import gcdm = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if isPrimeMR(g): return gelif isPrimeMR(n // g): return n // greturn findFactorRho(g)def primeFactor(n):i = 2ret = {}rhoFlg = 0while i*i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += 1 + i % 2if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}return retdef divisors(n):res = [1]prime = primeFactor(n)for p in prime:newres = []for d in res:for j in range(prime[p]+1):newres.append(d*p**j)res = newresreturn resfor _ in range(int(input())):a,b = mi()A,B = a,bg = gcd(a,b)a,b = a//g,b//gres = []for i in range(59,-1,-1):if a>>i & 1 and b>>i & 1:a -= 2**ib -= 2**ielif not (a>>i & 1 == 0 and b>>i & 1 == 0):breakif a:while a.bit_length() < b.bit_length():res.append(a&(-a))a += a&(-a)b -= afor i in range(59,-1,-1):if b>>i & 1:res.append(1<<i)for i in range(len(res)):res[i] *= gprint(len(res))print(*res)for g in res:assert A%g==0A += gassert A==Bassert len(res) <= 120