結果

問題 No.864 四方演算
ユーザー lavox
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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) = K
int 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()); }
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0