結果
問題 |
No.3081 Make Palindromic Multiple
|
ユーザー |
|
提出日時 | 2025-03-28 22:57:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 79 ms / 1,000 ms |
コード長 | 4,989 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 82,648 KB |
実行使用メモリ | 73,972 KB |
最終ジャッジ日時 | 2025-03-28 22:58:01 |
合計ジャッジ時間 | 5,060 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
ソースコード
# input import sys input = sys.stdin.readline II = lambda : int(input()) MI = lambda : map(int, input().split()) LI = lambda : [int(a) for a in input().split()] SI = lambda : input().rstrip() LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)] LSI = lambda n : [input().rstrip() for _ in range(n)] MI_1 = lambda : map(lambda x:int(x)-1, input().split()) LI_1 = lambda : [int(a)-1 for a in input().split()] def graph(n:int, m:int, dir:bool=False, index:int=-1) -> list[set[int]]: edge = [set() for i in range(n+1+index)] for _ in range(m): a,b = map(int, input().split()) a += index b += index edge[a].add(b) if not dir: edge[b].add(a) return edge def graph_w(n:int, m:int, dir:bool=False, index:int=-1) -> list[set[tuple]]: edge = [set() for i in range(n+1+index)] for _ in range(m): a,b,c = map(int, input().split()) a += index b += index edge[a].add((b,c)) if not dir: edge[b].add((a,c)) return edge mod = 998244353 inf = 1001001001001001001 ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97 ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97 yes = lambda : print("Yes") no = lambda : print("No") yn = lambda flag : print("Yes" if flag else "No") def acc(a:list[int]): sa = [0]*(len(a)+1) for i in range(len(a)): sa[i+1] = a[i] + sa[i] return sa prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1) alplow = "abcdefghijklmnopqrstuvwxyz" alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)} DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]] DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]] prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59] sys.set_int_max_str_digits(0) sys.setrecursionlimit(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') from collections import defaultdict,deque from heapq import heappop,heappush from bisect import bisect_left,bisect_right DD = defaultdict BSL = bisect_left BSR = bisect_right from math import isqrt from random import randint def gcd(x, y): """ x < y """ while y: x, y = y, x%y return x def is_prime(num): """ 1 <= x < 1<<64 """ if num < 4: return num > 1 if not num&1: return False d, s = num-1, 0 while not d&1: d >>= 1 s += 1 tests = (2,7,61) if num < 4759123141 else (2,325,9375,28178,450775,9780504,1795265022) for test in tests: if test >= num: return True t = pow(test, d, num) if 1 < t < num-1: for _ in range(s-1): t = t*t%num if t == num-1: break else: return False return True def find_prime(n): b = n.bit_length() - 1 b = (b >> 2) << 2 m = (1 << (b >> 3)) << 1 while True: c = randint(1, n - 1) y = 0 g = q = r = 1 while g == 1: x = y for _ in range(r): y = (y * y + c) % n k = 0 while k < r and g == 1: ys = y for _ in range(min(m, r - k)): y = (y * y + c) % n q = q * abs(x - y) % n g = gcd(q, n) k += m r <<= 1 if g == n: g = 1 y = ys while g == 1: y = (y * y + c) % n g = gcd(abs(x - y), n) if g == n: continue if is_prime(g): return g elif is_prime(n // g): return n // g else: n = g def primefact(n): result = dict() for p in range(2, 500): if p * p > n: break c = 0 while n%p == 0: n //= p c += 1 if c: result[p] = c while n > 1 and not is_prime(n): p = find_prime(n) c = 0 while n % p == 0: n //= p c += 1 result[p] = c if n > 1: result[n] = 1 return result n = II() m = n if n < 10: print(1) print(n, 1) exit() tmp = 1 d = 1 while n%2 == 0: n //= 2 tmp *= 2 d += 1 while n%5 == 0: n //= 5 tmp *= 5 d += 1 print(2) def calc(d, n, tmp): deg = (10**(d+1) - 1) * n pf = primefact(deg) for p, c in pf.items(): if tmp * p**c <= 10 ** d: tmp *= p**c deg //= p**c else: deg *= p-1 deg //= p s = str(tmp) s = "0" * (d - len(s)) + s revs = s[::-1] # print(deg, d, n) if deg > 10 ** 18: return False print(revs, deg) print(s, deg) exit() while True: calc(d, n, tmp) d += 1 assert deg <= 10 ** 18 # ans = revs*deg + s*deg # print(n, int(ans) % m)