結果
問題 | No.864 四方演算 |
ユーザー |
|
提出日時 | 2021-08-31 19:14:50 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 98 ms / 1,000 ms |
コード長 | 3,298 bytes |
コンパイル時間 | 2,114 ms |
コンパイル使用メモリ | 78,228 KB |
実行使用メモリ | 51,732 KB |
最終ジャッジ日時 | 2024-11-26 02:34:03 |
合計ジャッジ時間 | 6,078 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.util.ArrayList;import java.util.Arrays;import java.util.NoSuchElementException;public class Main {public static void main(String[] args) {Main o = new Main();o.solve();}public void solve() {FastScanner sc = new FastScanner(System.in);long N = sc.nextLong();long K = sc.nextLong();// (a + c)(b + d) = Kint MAX = 1000005;boolean[] p = new boolean[MAX + 1];Arrays.fill(p, true);ArrayList<Factor> F = new ArrayList<>();long K0 = K;for ( int n = 2 ; ((long)n) * (long)n <= K0 ; n++ ) {if ( !p[n] ) continue;p[n] = true;int cur = n;while ( (cur += n) <= MAX ) {p[cur] = false;}int cnt = 0;while ( K0 % (long)n == 0 ) {cnt++;K0 = K0 / (long) n;}if ( cnt > 0 ) {F.add(new Factor(n, cnt));}}if ( K0 > 1 ) {F.add(new Factor(K0, 1));}long ans = rec(F, 0, 1, N, K);System.out.println(ans);}long rec(ArrayList<Factor> F, int i, long p, long N, long K) {if ( i >= F.size() ) {long q = K / p;return count(p, N) * count(q, N);}long ret = 0;long P = p;Factor f = F.get(i);for ( int j = 0 ; j <= f.pow ; j++ ) {ret += rec(F, i + 1, P, N, K);P = P * f.p;}return ret;}long count(long n, long N) {long min = Math.max(1, n - N);long max = Math.min(n - 1, N);return Math.max(max - min + 1, 0);}class Factor {long p = 0;int pow = 0;Factor( long p, int pow ) {this.p = p;this.pow = pow;}}class FastScanner {private final InputStream in;private final byte[] buf = new byte[1024];private int ptr = 0;private int buflen = 0;FastScanner( InputStream source ) { this.in = source; }private boolean hasNextByte() {if ( ptr < buflen ) return true;else {ptr = 0;try { buflen = in.read(buf); } catch (IOException e) { e.printStackTrace(); }if ( buflen <= 0 ) return false;}return true;}private int readByte() { if ( hasNextByte() ) return buf[ptr++]; else return -1; }private boolean isPrintableChar( int c ) { return 33 <= c && c <= 126; }private boolean isNumeric( int c ) { return '0' <= c && c <= '9'; }private void skipToNextPrintableChar() { while ( hasNextByte() && !isPrintableChar(buf[ptr]) ) ptr++; }public boolean hasNext() { skipToNextPrintableChar(); return hasNextByte(); }public String next() {if ( !hasNext() ) throw new NoSuchElementException();StringBuilder ret = new StringBuilder();int b = readByte();while ( isPrintableChar(b) ) { ret.appendCodePoint(b); b = readByte(); }return ret.toString();}public long nextLong() {if ( !hasNext() ) throw new NoSuchElementException();long ret = 0;int b = readByte();boolean negative = false;if ( b == '-' ) { negative = true; if ( hasNextByte() ) b = readByte(); }if ( !isNumeric(b) ) throw new NumberFormatException();while ( true ) {if ( isNumeric(b) ) ret = ret * 10 + b - '0';else if ( b == -1 || !isPrintableChar(b) ) return negative ? -ret : ret;else throw new NumberFormatException();b = readByte();}}public int nextInt() { return (int)nextLong(); }public double nextDouble() { return Double.parseDouble(next()); }}}