結果

問題 No.644 G L C C D M
ユーザー uwi
提出日時 2018-02-02 21:31:30
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 114 ms
コード長 3,415 Byte
コンパイル時間 2,651 ms
使用メモリ 32,192 KB
最終ジャッジ日時 2019-06-24 06:34:30

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
Sample1.txt AC 82 ms
31,856 KB
Sample2.txt AC 79 ms
31,956 KB
Sample3.txt AC 80 ms
32,020 KB
Sample4.txt AC 81 ms
32,168 KB
test1.txt AC 80 ms
31,848 KB
test2.txt AC 81 ms
30,596 KB
test3.txt AC 79 ms
30,732 KB
test4.txt AC 79 ms
32,192 KB
test5.txt AC 80 ms
31,552 KB
test6.txt AC 81 ms
31,736 KB
test7.txt AC 81 ms
31,316 KB
test8.txt AC 81 ms
29,748 KB
test9.txt AC 80 ms
32,184 KB
test10.txt AC 83 ms
31,948 KB
test11.txt AC 82 ms
31,492 KB
test12.txt AC 79 ms
30,584 KB
test13.txt AC 80 ms
28,844 KB
test14.txt AC 81 ms
30,576 KB
test15.txt AC 107 ms
31,752 KB
test16.txt AC 80 ms
31,484 KB
test17.txt AC 81 ms
30,572 KB
test18.txt AC 79 ms
32,184 KB
test19.txt AC 114 ms
31,472 KB
test20.txt AC 110 ms
29,856 KB
test21.txt AC 109 ms
30,464 KB
test22.txt AC 89 ms
31,436 KB
test23.txt AC 88 ms
30,840 KB
テストケース一括ダウンロード

ソースコード

diff #
package contest180202;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class C {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), m = ni();
		int mod = 1000000007;
		long[] num = new long[100005];
		for(int i = n;i >= 1;i--){
			num[i] = ((long)(n/i) * (n/i) - n/i);
			for(int j = i*2;j <= n;j+=i){
				num[i] -= num[j];
			}
			num[i] %= mod;
			if(num[i] < 0)num[i] += mod;
			if(i == m){
				for(int j = 1;j <= n-2;j++)num[i] = num[i] * j % mod;
				out.println(num[i]);
				return;
			}
		}
		out.println(0);
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new C().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
0