結果

問題 No.575 n! / m / m / m...
ユーザー hiromi_ayasehiromi_ayase
提出日時 2017-10-07 01:03:20
言語 Java21
(openjdk 21)
結果
AC  
実行時間 173 ms / 2,000 ms
コード長 7,065 bytes
コンパイル時間 5,460 ms
コンパイル使用メモリ 93,820 KB
実行使用メモリ 58,468 KB
最終ジャッジ日時 2023-08-10 18:27:49
合計ジャッジ時間 9,845 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 157 ms
58,116 KB
testcase_01 AC 166 ms
58,076 KB
testcase_02 AC 154 ms
57,896 KB
testcase_03 AC 156 ms
58,172 KB
testcase_04 AC 154 ms
58,200 KB
testcase_05 AC 159 ms
58,172 KB
testcase_06 AC 155 ms
58,268 KB
testcase_07 AC 156 ms
58,360 KB
testcase_08 AC 156 ms
57,944 KB
testcase_09 AC 155 ms
58,220 KB
testcase_10 AC 152 ms
58,212 KB
testcase_11 AC 160 ms
58,124 KB
testcase_12 AC 167 ms
58,328 KB
testcase_13 AC 162 ms
58,248 KB
testcase_14 AC 171 ms
58,240 KB
testcase_15 AC 162 ms
58,368 KB
testcase_16 AC 165 ms
58,208 KB
testcase_17 AC 160 ms
58,096 KB
testcase_18 AC 173 ms
58,288 KB
testcase_19 AC 166 ms
58,252 KB
testcase_20 AC 161 ms
58,468 KB
testcase_21 AC 168 ms
58,220 KB
testcase_22 AC 170 ms
57,992 KB
testcase_23 AC 168 ms
58,188 KB
testcase_24 AC 170 ms
58,136 KB
testcase_25 AC 163 ms
58,164 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.Random;

class FactorL {

	static long[][] factorX(long n, int[] primes)
	{
		long[][] ret = new long[20][2];
		int rp = 0;
		for(int p : primes){
			if((long)p * p > n)break;
			int i;
			for(i = 0;n % p == 0;n /= p, i++);
			if(i > 0){
				ret[rp][0] = p;
				ret[rp][1] = i;
				rp++;
			}
		}
		if(n == 1)return Arrays.copyOf(ret, rp);
		
		// P^2
		long sq = (long)Math.sqrt(n);
		for(long u = Math.max(2, sq-2);u <= sq+2;u++){
			if(u*u == n){
				ret[rp][0] = u;
				ret[rp][1] = 2;
				rp++;
				return Arrays.copyOf(ret, rp);
			}
		}
		
		// Prime
		if(doMirrorRabin(n)){
			ret[rp][0] = n;
			ret[rp][1] = 1;
			rp++;
			return Arrays.copyOf(ret, rp);
		}
		
		// P*Q
		long f = rho(n);
		if(f == -1)throw new ArithmeticException();
		if(f > n/f)f = n/f;
		ret[rp][0] = f; ret[rp][1] = 1; rp++;
		ret[rp][0] = n/f; ret[rp][1] = 1; rp++;
		return Arrays.copyOf(ret, rp);
	}
	
	public static long mul(long a, long b, long mod)
	{
		a %= mod;
		long ret = 0;
		int x = 63-Long.numberOfLeadingZeros(b);
		for(;x >= 0;x--){
			ret += ret;
			if(ret >= mod)ret -= mod;
			if(b<<~x<0){
				ret += a;
				if(ret >= mod)ret -= mod;
			}
		}
		return ret;
	}
	
	public static boolean doMirrorRabin(long n)
	{
//		int[] P = {2, 7, 61}; // n<4759123141
		int[] P = {2,3,5,7,11,13,17,19,23}; // n=long
		int s = Long.numberOfTrailingZeros(n-1);
		long d = n-1>>s;
		outer:
		for(int a : P){
			if(a >= n)continue;
			
			long mul = a;
			long ad = 1;
			for(long e = d;e > 0;e>>>=1){
				if((e&1)==1)ad = mul(ad, mul, n);
				mul = mul(mul, mul, n);
			}
			if(ad == 1)continue;
			
			for(int r = 0;r < s;r++){
				if(ad == n-1)continue outer;
				ad = mul(ad, ad, n);
			}
			return false;
		}
		return true;
	}

	static long rho(long n)
	{
		Random gen = new Random();
		for(int u = 0;u < 100;u++){
			long ran = (gen.nextLong()&Long.MAX_VALUE) % n;
			long x = 2, y = 2, d = 1;
			while(d == 1){
				x = (mul(x, x, n)+ran)%n;
				y = (mul(y, y, n)+ran)%n;
				y = (mul(y, y, n)+ran)%n;
				d = gcd(Math.abs(x-y), n);
			}
			if(d < n)return d;
		}
		return -1;
	}
	
	public static long gcd(long a, long b) {
		while (b > 0){
			long c = a;
			a = b;
			b = c % b;
		}
		return a;
	}
	
	
	public static int[] sieveEratosthenes(int n) {
		if(n <= 32){
			int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
			for(int i = 0;i < primes.length;i++){
				if(n < primes[i]){
					return Arrays.copyOf(primes, i);
				}
			}
			return primes;
		}

		int u = n + 32;
		double lu = Math.log(u);
		int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
		ret[0] = 2;
		int pos = 1;

		int[] isp = new int[(n + 1) / 32 / 2 + 1];
		int sup = (n + 1) / 32 / 2 + 1;

		int[] tprimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
		for(int tp : tprimes){
			ret[pos++] = tp;
			int[] ptn = new int[tp];
			for(int i = (tp - 3) / 2;i < tp << 5;i += tp)
				ptn[i >> 5] |= 1 << (i & 31);
			for(int i = 0;i < tp;i++){
				for(int j = i;j < sup;j += tp)
					isp[j] |= ptn[i];
			}
		}

		// 3,5,7
		// 2x+3=n
		int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4,
				13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 };
		int h = n / 2;
		for(int i = 0;i < sup;i++){
			for(int j = ~isp[i];j != 0;j &= j - 1){
				int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
				int p = 2 * pp + 3;
				if(p > n)
					break;
				ret[pos++] = p;
				for(int q = pp;q <= h;q += p)
					isp[q >> 5] |= 1 << (q & 31);
			}
		}

		return Arrays.copyOf(ret, pos);
	}
}


public class Main {

	//v = 1.2024234005160768
	//e = 65657059

	static int[] primes = FactorL.sieveEratosthenes(2000000);
	static double EPS = 0.000000000000001;
	private static void solve() {
		long n = nl();
		long m = nl();
		
		long d = div(n, m);
		double f = factor(n);

		String ret = calc(f, m, d);
		System.out.println(ret);
	}
	
	private static double factor(double n) {
		
		double ret = 0;
		
		if (n < 5000000) {
			for (long i = 1; i <= n; i ++) {
				ret += Math.log(i);
			}
		} else {
			ret = Math.log(Math.PI * 2 / (n + 1)) /2 + Math.log((n + 1) / Math.E) * (n + 1);
		}
		return ret / Math.log(10);
	}

	private static String calc(double logFactorN, long m, long d) {
		double ret = logFactorN;
		long e1 = (long)(ret + EPS);
		ret -= e1;

		double div = d * Math.log10(m);
		long e2 = (long)(div + EPS);
		div -= e2;

		e1 -= e2;
		ret -= div;
		
		double v = Math.pow(10, ret);
		while (v < 1) {
			e1 --;
			v *= 10;
		}

		return String.format("%.4fe%d\n", v, e1);
	}

	private static long div(long n, long m) {
		long[][] f = FactorL.factorX(m, primes);
		
		long[] count = new long[f.length];
		for (int i = 0; i < f.length; i ++) {
			long x = n;
			while (x > 0) {
				count[i] += x / f[i][0];
				x /= f[i][0];
			}
		}
		
		long min = Long.MAX_VALUE;
		for (int i = 0; i < f.length; i ++) {
			min = Math.min(count[i] / f[i][1], min);
		}
		return min;
	}

	
	public static void main(String[] args) {
		new Thread(null, new Runnable() {
			@Override
			public void run() {
				long start = System.currentTimeMillis();
				String debug = args.length > 0 ? args[0] : null;
				if (debug != null) {
					try {
						is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
					} catch (Exception e) {
						throw new RuntimeException(e);
					}
				}
				reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
				solve();
				out.flush();
				tr((System.currentTimeMillis() - start) + "ms");
			}
		}, "", 64000000).start();
	}

	private static java.io.InputStream is = System.in;
	private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
	private static java.util.StringTokenizer tokenizer = null;
	private static java.io.BufferedReader reader;

	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new java.util.StringTokenizer(reader.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	private static double nd() {
		return Double.parseDouble(next());
	}

	private static long nl() {
		return Long.parseLong(next());
	}

	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private static char[] ns() {
		return next().toCharArray();
	}

	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}

	private static int[][] ntable(int n, int m) {
		int[][] table = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				table[i][j] = ni();
			}
		}
		return table;
	}

	private static int[][] nlist(int n, int m) {
		int[][] table = new int[m][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				table[j][i] = ni();
			}
		}
		return table;
	}

	private static int ni() {
		return Integer.parseInt(next());
	}

	private static void tr(Object... o) {
		if (is != System.in)
			System.out.println(java.util.Arrays.deepToString(o));
	}
}
0