Trailing Loves (or L’oeufs?)
https://codeforces.com/contest/1114/problem/C
考え方
題意
\( 10 \) 進数で与えられた自然数 \( n \) の階乗を \( b \) 進数で表したときの \( 0 \) の個数を答えます。
方針
まずは、\( 10 \) 進数のときを考えます。良くある問題で、\( n! \) に現れる \( 0 \) の個数を求める問題があります。これは、\( 10 \) の最大の素因数である \( 5 \) を用いて、\( n \) までに \( 5^k \ ( 5^k \leq n ) \) で割ることができるの数の和が答えになります。これは、\( n! \) を素因数分解したときの \( 5 \) の個数となります。
\( b \) 進数のときでは、\( b \) の素因数を求めます。また、このときに、素因数の個数もカウントします。例えば、\( 18 \) は \(18 = 2 \times 3^2 \) なので、\( 2 \) の個数は \( 1 \) で \( 3 \) の個数は \( 2 \) となります。
次に各素因数 \( p_i \) について、\( n! \) に現れる \( p_i\) の個数を \( b \) に現れる \( p_i\) の個数で割ります。この値の最小値が答えになります。
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class ProblemC { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); long b = sc.nextLong(); sc.close(); long t = b; Map<Long, Long> m = new HashMap<Long, Long>(); for(long i = 2; i * i <= b; i++) { while(t % i == 0) { t /= i; m.merge(i, 1l, (v1, v2) -> v1 + v2); } } if(t != 1) { m.put(t, 1l); } long[] c = new long[m.size()]; int idx = 0; for(long k : m.keySet()) { long s = n; while(s > 0) { c[idx] += s / k; s /= k; } c[idx] /= m.get(k); idx++; } Arrays.sort(c); System.out.println(c[0]); } } |
感想
なんでこのようにして求められるかいまいちピンときていませんが、こういうものだと覚えておきます。