QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#512094 | #9167. Coprime Array | ucup-team133# | AC ✓ | 16ms | 11208kb | Python3 | 5.6kb | 2024-08-10 13:30:23 | 2024-08-10 13:30:24 |
Judging History
answer
import sys
from itertools import permutations
from heapq import heappop,heappush
from collections import deque
import random
import bisect
from math import gcd
input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())
def floor_sum(n: int, m: int, a: int, b: int) -> int:
ans = 0
if a >= m:
ans += (n - 1) * n * (a // m) // 2
a %= m
if b >= m:
ans += n * (b // m)
b %= m
y_max = (a * n + b) // m
x_max = y_max * m - b
if y_max == 0:
return ans
ans += (n - (x_max + a - 1) // a) * y_max
ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
return ans
def _inv_gcd(a,b):
a %= b
if a == 0:
return (b, 0)
# Contracts:
# [1] s - m0 * a = 0 (mod b)
# [2] t - m1 * a = 0 (mod b)
# [3] s * |m1| + t * |m0| <= b
s = b
t = a
m0 = 0
m1 = 1
while t:
u = s // t
s -= t * u
m0 -= m1 * u # |m1 * u| <= |m1| * s <= b
# [3]:
# (s - t * u) * |m1| + t * |m0 - m1 * u|
# <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
# = s * |m1| + t * |m0| <= b
s, t = t, s
m0, m1 = m1, m0
# by [3]: |m0| <= b/g
# by g != b: |m0| < b/g
if m0 < 0:
m0 += b // s
return (s, m0)
def crt(r,m):
assert len(r) == len(m)
n = len(r)
# Contracts: 0 <= r0 < m0
r0 = 0
m0 = 1
for i in range(n):
assert 1 <= m[i]
r1 = r[i] % m[i]
m1 = m[i]
if m0 < m1:
r0, r1 = r1, r0
m0, m1 = m1, m0
if m0 % m1 == 0:
if r0 % m1 != r1:
return (0, 0)
continue
# assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)
'''
(r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
r2 % m0 = r0
r2 % m1 = r1
-> (r0 + x*m0) % m1 = r1
-> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
-> x = (r1 - r0) / g * inv(u0) (mod u1)
'''
# im = inv(u0) (mod u1) (0 <= im < u1)
g, im = _inv_gcd(m0, m1)
u1 = m1 // g
# |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
if (r1 - r0) % g:
return (0, 0)
# u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
x = (r1 - r0) // g % u1 * im % u1
'''
|r0| + |m0 * x|
< m0 + m0 * (u1 - 1)
= m0 + m0 * m1 / g - m0
= lcm(m0, m1)
'''
r0 += x * m0
m0 *= u1 # -> lcm(m0, m1)
if r0 < 0:
r0 += m0
return (r0, m0)
def isPrimeMR(n):
if n==1:
return 0
d = n - 1
d = d // (d & -d)
L = [2, 3, 5, 7, 11, 13, 17]
if n in L:
return 1
for a in L:
t = d
y = pow(a, t, n)
if y == 1: continue
while y != n - 1:
y = (y * y) % n
if y == 1 or t == n - 1: return 0
t <<= 1
return 1
def findFactorRho(n):
from math import gcd
m = 1 << n.bit_length() // 8
for c in range(1, 99):
f = lambda x: (x * x + c) % n
y, r, q, g = 2, 1, 1, 1
while g == 1:
x = y
for i in range(r):
y = f(y)
k = 0
while k < r and g == 1:
ys = y
for i in range(min(m, r - k)):
y = f(y)
q = q * abs(x - y) % n
g = gcd(q, n)
k += m
r <<= 1
if g == n:
g = 1
while g == 1:
ys = f(ys)
g = gcd(abs(x - ys), n)
if g < n:
if isPrimeMR(g): return g
elif isPrimeMR(n // g): return n // g
return findFactorRho(g)
def primeFactor(n):
i = 2
ret = {}
rhoFlg = 0
while i*i <= n:
k = 0
while n % i == 0:
n //= i
k += 1
if k: ret[i] = k
i += 1 + i % 2
if i == 101 and n >= 2 ** 20:
while n > 1:
if isPrimeMR(n):
ret[n], n = 1, 1
else:
rhoFlg = 1
j = findFactorRho(n)
k = 0
while n % j == 0:
n //= j
k += 1
ret[j] = k
if n > 1: ret[n] = 1
if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
return ret
def solve(s,x):
if gcd(s,x) == 1:
return [s]
if s & 1 == 1 and x & 1 == 0:
res = solve(s-1,x)
return [1] + res
"""
[s+t,-t] such that
t != 0 mod p
t != -s mod p
"""
pf = primeFactor(x)
R = []
M = []
for p in pf:
for r in range(1,p):
if r!=((s) % p):
R.append(r)
M.append(p)
break
else:
assert False
t,m = crt(R,M)
assert gcd(s-t,p) == 1
assert gcd(t,p) == 1
return [s-t,t]
def brute(s,x):
if gcd(s,x) == 1:
return [s]
for t in range(-1000,1000):
if gcd(abs(s+t),x) == 1 and gcd(abs(t),x) == 1:
return [s+t,-t]
return [1,1,s-2]
while False:
s,x = random.randint(2,10**9),random.randint(2,10**9)
A = solve(s,x)
print(A)
assert max(abs(a) for a in A) <= 10**9
s,x = mi()
A = solve(s,x)
assert sum(A) == s
print(len(A))
print(*A)
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 15ms
memory: 11088kb
input:
9 6
output:
3 1 7 1
result:
ok Correct
Test #2:
score: 0
Accepted
time: 15ms
memory: 11052kb
input:
14 34
output:
2 13 1
result:
ok Correct
Test #3:
score: 0
Accepted
time: 16ms
memory: 10980kb
input:
1000000000 223092870
output:
2 851271419 148728581
result:
ok Correct
Test #4:
score: 0
Accepted
time: 8ms
memory: 11048kb
input:
2 1000000000
output:
2 1 1
result:
ok Correct
Test #5:
score: 0
Accepted
time: 6ms
memory: 11164kb
input:
649557664 933437700
output:
2 649473683 83981
result:
ok Correct
Test #6:
score: 0
Accepted
time: 11ms
memory: 11204kb
input:
33396678 777360870
output:
2 33396677 1
result:
ok Correct
Test #7:
score: 0
Accepted
time: 9ms
memory: 11140kb
input:
48205845 903124530
output:
3 1 48187033 18811
result:
ok Correct
Test #8:
score: 0
Accepted
time: 15ms
memory: 11136kb
input:
251037078 505905400
output:
2 251037077 1
result:
ok Correct
Test #9:
score: 0
Accepted
time: 15ms
memory: 11024kb
input:
30022920 172746860
output:
2 30022919 1
result:
ok Correct
Test #10:
score: 0
Accepted
time: 4ms
memory: 11124kb
input:
63639298 808058790
output:
2 63390587 248711
result:
ok Correct
Test #11:
score: 0
Accepted
time: 11ms
memory: 11208kb
input:
76579017 362768406
output:
3 1 76579015 1
result:
ok Correct
Test #12:
score: 0
Accepted
time: 15ms
memory: 11040kb
input:
40423669 121437778
output:
3 1 40423667 1
result:
ok Correct
Test #13:
score: 0
Accepted
time: 15ms
memory: 11040kb
input:
449277309 720915195
output:
2 449277308 1
result:
ok Correct
Test #14:
score: 0
Accepted
time: 15ms
memory: 11128kb
input:
81665969 919836918
output:
3 1 81597899 68069
result:
ok Correct
Test #15:
score: 0
Accepted
time: 15ms
memory: 11012kb
input:
470578680 280387800
output:
2 470578679 1
result:
ok Correct
Test #16:
score: 0
Accepted
time: 9ms
memory: 11052kb
input:
58450340 803305503
output:
2 58450339 1
result:
ok Correct
Test #17:
score: 0
Accepted
time: 15ms
memory: 11036kb
input:
125896113 323676210
output:
3 1 125836831 59281
result:
ok Correct
Test #18:
score: 0
Accepted
time: 15ms
memory: 11076kb
input:
381905348 434752500
output:
2 381905347 1
result:
ok Correct
Test #19:
score: 0
Accepted
time: 15ms
memory: 11184kb
input:
78916498 653897673
output:
1 78916498
result:
ok Correct
Test #20:
score: 0
Accepted
time: 11ms
memory: 11048kb
input:
35787885 270845190
output:
3 1 35787883 1
result:
ok Correct
Extra Test:
score: 0
Extra Test Passed