結果
問題 | No.1809 Divide NCK |
ユーザー | U S |
提出日時 | 2022-01-14 23:06:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,860 bytes |
コンパイル時間 | 179 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 63,968 KB |
最終ジャッジ日時 | 2024-04-30 16:56:49 |
合計ジャッジ時間 | 3,957 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 54 ms
62,412 KB |
testcase_01 | AC | 68 ms
61,744 KB |
testcase_02 | AC | 54 ms
61,812 KB |
testcase_03 | AC | 53 ms
62,080 KB |
testcase_04 | AC | 53 ms
61,892 KB |
testcase_05 | AC | 53 ms
62,352 KB |
testcase_06 | AC | 54 ms
62,276 KB |
testcase_07 | AC | 54 ms
62,580 KB |
testcase_08 | AC | 53 ms
62,604 KB |
testcase_09 | AC | 52 ms
61,372 KB |
testcase_10 | AC | 54 ms
62,332 KB |
testcase_11 | AC | 66 ms
62,864 KB |
testcase_12 | AC | 68 ms
62,080 KB |
testcase_13 | AC | 57 ms
62,948 KB |
testcase_14 | AC | 60 ms
62,148 KB |
testcase_15 | AC | 55 ms
62,000 KB |
testcase_16 | AC | 68 ms
62,988 KB |
testcase_17 | AC | 54 ms
63,056 KB |
testcase_18 | AC | 67 ms
63,024 KB |
testcase_19 | AC | 68 ms
62,328 KB |
testcase_20 | AC | 66 ms
62,184 KB |
testcase_21 | AC | 64 ms
62,980 KB |
testcase_22 | AC | 55 ms
62,728 KB |
testcase_23 | AC | 54 ms
62,268 KB |
testcase_24 | AC | 54 ms
62,480 KB |
testcase_25 | AC | 53 ms
62,416 KB |
testcase_26 | AC | 55 ms
62,048 KB |
testcase_27 | AC | 55 ms
62,536 KB |
testcase_28 | AC | 54 ms
61,740 KB |
testcase_29 | AC | 65 ms
62,028 KB |
testcase_30 | AC | 68 ms
63,420 KB |
testcase_31 | AC | 57 ms
63,592 KB |
testcase_32 | AC | 63 ms
63,444 KB |
testcase_33 | AC | 62 ms
62,672 KB |
testcase_34 | AC | 64 ms
62,144 KB |
testcase_35 | AC | 63 ms
62,700 KB |
testcase_36 | AC | 62 ms
62,488 KB |
testcase_37 | AC | 66 ms
63,584 KB |
testcase_38 | AC | 62 ms
63,968 KB |
testcase_39 | AC | 67 ms
63,760 KB |
testcase_40 | AC | 68 ms
62,276 KB |
testcase_41 | AC | 64 ms
62,916 KB |
ソースコード
# import sys # input = sys.stdin.readline def mp():return map(int,input().split()) def lmp():return list(map(int,input().split())) def mps(A):return [tuple(map(int, input().split())) for _ in range(A)] def stoi(LIST):return list(map(int,LIST)) def itos(LIST):return list(map(str,LIST)) def bitA(X,A):return X & 1<<A == 1<<A import math import bisect import heapq import time from copy import copy as cc from copy import deepcopy as dc from itertools import accumulate from collections import Counter, defaultdict, deque def ceil(U,V):return (U+V-1)//V def modf1(N,MOD):return (N-1)%MOD+1 inf = int(1e18+20) mod = int(1e9+7) def seg_insu(x,M): return insu(x,M)-insu(x-k,M) def insu(x,M): ans = 0 now = M while now <= x: ans += x//now now *= M return ans def factorization(n): arr = [] temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr.append([i, cnt]) if temp!=1: arr.append([temp, 1]) if arr==[]: arr.append([n, 1]) return arr n,k,m = mp() mfact = factorization(m) #print(mfact) ans = 0 bl = len(mfact) u = [] for i,j in mfact: u.append((seg_insu(n,i)-seg_insu(k,i))//j) print(min(u)) # for i in range(1,1<<bl): # tar = [] # cnt = 1 # for j in range(bl): # if bitA(i,j): # cnt += mfact[j][0]**mfact[j][1] # tar.append(mfact[j]) # bunsi = [] # bunbo = [] # y = [] # y.append(cnt) # u = inf # v = inf # for num,f in tar: # u = min(u,seg_insu()) # now = inf # for num, f in tar: # now = min(now, (seg_insu(n,num)-seg_insu(k,num))//f) # if len(tar) % 2 == 1: # ans += now # else: # ans -= now # print(ans,tar) #print(ans)