結果
問題 | No.2181 LRM Question 2 |
ユーザー | shobonvip |
提出日時 | 2023-01-07 00:30:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 541 ms / 2,000 ms |
コード長 | 2,432 bytes |
コンパイル時間 | 377 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 99,288 KB |
最終ジャッジ日時 | 2024-05-08 00:16:17 |
合計ジャッジ時間 | 5,529 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
68,352 KB |
testcase_01 | AC | 59 ms
68,876 KB |
testcase_02 | AC | 307 ms
90,712 KB |
testcase_03 | AC | 60 ms
68,516 KB |
testcase_04 | AC | 63 ms
71,008 KB |
testcase_05 | AC | 61 ms
68,960 KB |
testcase_06 | AC | 63 ms
71,380 KB |
testcase_07 | AC | 59 ms
69,228 KB |
testcase_08 | AC | 541 ms
99,288 KB |
testcase_09 | AC | 274 ms
90,572 KB |
testcase_10 | AC | 494 ms
99,260 KB |
testcase_11 | AC | 488 ms
99,008 KB |
testcase_12 | AC | 472 ms
98,712 KB |
testcase_13 | AC | 72 ms
74,268 KB |
testcase_14 | AC | 81 ms
81,844 KB |
testcase_15 | AC | 66 ms
71,576 KB |
testcase_16 | AC | 135 ms
87,576 KB |
testcase_17 | AC | 121 ms
79,720 KB |
testcase_18 | AC | 101 ms
78,760 KB |
testcase_19 | AC | 93 ms
78,744 KB |
testcase_20 | AC | 95 ms
80,876 KB |
testcase_21 | AC | 154 ms
81,992 KB |
testcase_22 | AC | 101 ms
79,060 KB |
testcase_23 | AC | 61 ms
68,148 KB |
testcase_24 | AC | 62 ms
68,060 KB |
testcase_25 | AC | 61 ms
68,088 KB |
ソースコード
import typing def inv_gcd(a: int, b: int) -> typing.Tuple[int, int]: a %= b if a == 0: return (b, 0) s = b t = a m0 = 0 m1 = 1 while t: u = s // t s -= t * u m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 if m0 < 0: m0 += b // s return (s, m0) def inv_mod(x: int, m: int) -> int: z = inv_gcd(x, m) return z[1] def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]: r0 = 0 m0 = 1 for r1, m1 in zip(r, m): r1 %= m1 if m0 < m1: r0, r1 = r1, r0 m0, m1 = m1, m0 if m0 % m1 == 0: if r0 % m1 != r1: return (0, 0) continue g, im = inv_gcd(m0, m1) u1 = m1 // g if (r1 - r0) % g: return (0, 0) x = (r1 - r0) // g % u1 * im % u1 r0 += x * m0 m0 *= u1 if r0 < 0:r0 += m0 return (r0, m0) def pfact(m): pf = {} for i in range(2,int(m**0.5)+1): while m%i == 0: pf[i] = pf.get(i,0) + 1 m //= i if m>1 : pf[m]=1 return pf def legendre(n, p): ret = 0 while n > 0: n //= p ret += n return ret l,r,m = map(int,input().split()) ans = (-2) * (r-l+1) % m pf = pfact(m) v = [[] for i in range(r-l+1)] pl = [] for p, cnt in pf.items(): mod = p ** cnt pl.append(mod) euler = (p-1) * p ** (cnt-1) vvv = [1] * (euler + 1) cc = 1 ww = 1 while cc <= euler: if ww % p == 0: ww += 1 continue vvv[cc] = vvv[cc-1] * ww % mod ww += 1 cc += 1 #print(vvv[-10:]) tmpm = 1 ggg = 2*l-2 while ggg > 0: #print(ggg) tmpm *= pow(vvv[euler], ggg // mod, mod) tmpm %= mod aim = ggg % mod for j in range(aim + 1): if j % p == 0: continue tmpm *= j tmpm %= mod ggg //= p #print() #print(tmpm, tmpz) tmpx = 1 ggg = l-1 while ggg > 0: tmpx *= pow(vvv[euler], ggg // mod, mod) tmpx %= mod aim = ggg % mod for j in range(aim + 1): if j % p == 0: continue tmpx *= j tmpx %= mod ggg //= p tmpz = inv_mod(tmpx, mod) tmpm *= tmpz * tmpz % mod tmpm %= mod tmpc = legendre(2*(l-1), p) - 2 * legendre(l-1, p) for i in range(l, r + 1): tt = i while tt % p == 0: tmpc -= 2 tt //= p tmpv = inv_mod(tt, mod) tmpm *= tmpv * tmpv tmpm %= mod tt = 2 * i - 1 while tt % p == 0: tmpc += 1 tt //= p tmpm *= tt tmpm %= mod tt = 2 * i while tt % p == 0: tmpc += 1 tt //= p tmpm *= tt tmpm %= mod if tmpc < cnt: v[i-l].append(tmpm * p ** tmpc % mod) else: v[i-l].append(0) for i in range(r-l+1): ans += crt(v[i], pl)[0] ans %= m print(ans)