#880445 (Java21) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	ゆうき
提出日時	2023-06-14 02:51:49
言語	Java21 (openjdk 21)
結果	AC
実行時間	854 ms / 3,000 ms
コード長	9,610 bytes
コンパイル時間	5,169 ms
コンパイル使用メモリ	105,060 KB
実行使用メモリ	79,000 KB
最終ジャッジ日時	2023-09-04 16:42:00
合計ジャッジ時間	28,828 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	60 ms 51,276 KB
testcase_01	AC	61 ms 50,856 KB
testcase_02	AC	61 ms 50,748 KB
testcase_03	AC	60 ms 50,960 KB
testcase_04	AC	60 ms 50,572 KB
testcase_05	AC	61 ms 50,672 KB
testcase_06	AC	60 ms 51,096 KB
testcase_07	AC	60 ms 50,484 KB
testcase_08	AC	59 ms 49,372 KB
testcase_09	AC	60 ms 50,780 KB
testcase_10	AC	60 ms 50,664 KB
testcase_11	AC	61 ms 50,480 KB
testcase_12	AC	60 ms 50,476 KB
testcase_13	AC	63 ms 50,940 KB
testcase_14	AC	60 ms 50,804 KB
testcase_15	AC	61 ms 50,512 KB
testcase_16	AC	60 ms 51,068 KB
testcase_17	AC	60 ms 51,084 KB
testcase_18	AC	60 ms 50,560 KB
testcase_19	AC	60 ms 50,464 KB
testcase_20	AC	97 ms 53,656 KB
testcase_21	AC	121 ms 54,052 KB
testcase_22	AC	123 ms 54,332 KB
testcase_23	AC	66 ms 51,212 KB
testcase_24	AC	66 ms 50,624 KB
testcase_25	AC	146 ms 56,564 KB
testcase_26	AC	128 ms 54,184 KB
testcase_27	AC	101 ms 53,248 KB
testcase_28	AC	102 ms 53,312 KB
testcase_29	AC	111 ms 54,160 KB
testcase_30	AC	112 ms 54,236 KB
testcase_31	AC	123 ms 53,992 KB
testcase_32	AC	134 ms 54,500 KB
testcase_33	AC	118 ms 54,232 KB
testcase_34	AC	118 ms 54,296 KB
testcase_35	AC	123 ms 54,280 KB
testcase_36	AC	119 ms 54,136 KB
testcase_37	AC	71 ms 51,312 KB
testcase_38	AC	72 ms 51,568 KB
testcase_39	AC	124 ms 54,984 KB
testcase_40	AC	122 ms 54,080 KB
testcase_41	AC	123 ms 54,476 KB
testcase_42	AC	126 ms 54,760 KB
testcase_43	AC	121 ms 54,376 KB
testcase_44	AC	123 ms 54,140 KB
testcase_45	AC	105 ms 53,788 KB
testcase_46	AC	105 ms 53,688 KB
testcase_47	AC	108 ms 51,800 KB
testcase_48	AC	138 ms 56,612 KB
testcase_49	AC	141 ms 56,848 KB
testcase_50	AC	122 ms 54,424 KB
testcase_51	AC	123 ms 54,336 KB
testcase_52	AC	107 ms 53,880 KB
testcase_53	AC	193 ms 58,912 KB
testcase_54	AC	530 ms 66,528 KB
testcase_55	AC	476 ms 66,588 KB
testcase_56	AC	494 ms 66,468 KB
testcase_57	AC	290 ms 61,244 KB
testcase_58	AC	329 ms 61,588 KB
testcase_59	AC	194 ms 58,944 KB
testcase_60	AC	294 ms 61,152 KB
testcase_61	AC	298 ms 61,492 KB
testcase_62	AC	481 ms 66,308 KB
testcase_63	AC	448 ms 66,564 KB
testcase_64	AC	350 ms 61,320 KB
testcase_65	AC	326 ms 61,208 KB
testcase_66	AC	66 ms 50,648 KB
testcase_67	AC	67 ms 50,688 KB
testcase_68	AC	552 ms 66,548 KB
testcase_69	AC	481 ms 66,696 KB
testcase_70	AC	528 ms 66,844 KB
testcase_71	AC	473 ms 66,636 KB
testcase_72	AC	451 ms 66,336 KB
testcase_73	AC	706 ms 78,008 KB
testcase_74	AC	799 ms 78,724 KB
testcase_75	AC	144 ms 56,848 KB
testcase_76	AC	500 ms 66,304 KB
testcase_77	AC	293 ms 61,176 KB
testcase_78	AC	695 ms 78,336 KB
testcase_79	AC	483 ms 66,688 KB
testcase_80	AC	686 ms 78,976 KB
testcase_81	AC	488 ms 66,576 KB
testcase_82	AC	101 ms 53,648 KB
testcase_83	AC	323 ms 61,268 KB
testcase_84	AC	322 ms 61,136 KB
testcase_85	AC	481 ms 66,540 KB
testcase_86	AC	624 ms 78,392 KB
testcase_87	AC	854 ms 76,576 KB
testcase_88	AC	848 ms 79,000 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.*;
import java.util.stream.*;
import java.awt.Point;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

class Solver{
  long st = System.currentTimeMillis();

  long elapsed(){ return System.currentTimeMillis() -st; }

  void reset(){ st = System.currentTimeMillis(); }

  static int infI = (int) 1e9;
  static long infL = (long) 1e18;
  static long mod = (int) 1e9 +7;
  //  static long mod = 998244353;
  static String yes = "Yes";
  static String no = "No";

  Random rd = ThreadLocalRandom.current();
  MyReader in = new MyReader(System.in);
  MyWriter out = new MyWriter(System.out);
  MyWriter log = new MyWriter(System.err){
    @Override
    protected void ln(){
      super.ln();
      flush();
    };
  };

  int N = in.it();

  Object solve(){

    int[] PN = primes(N).stream().toArray();
    BitSet primes = primes(3 *N);
    int[] P3N = primes.stream().toArray();

    long[] A = new long[N +1];
    for (var l:PN)
      A[l] = 1;
    long[] X = FastFourierTransform.multiply(A,A);
    X = FastFourierTransform.multiply(X,A);

    long ans = 0;

    for (var p:P3N)
      ans += X[p];
    for (var a:PN)
      for (var b:PN)
        if (primes.get(a *2 +b))
          ans -= 3;

    return ans /6;
  }

  BitSet primes(int b){
    BitSet ret = new BitSet(b);
    ret.set(2,b +1);
    for (int p = 2;p *p <= b;p++)
      if (ret.get(p))
        for (int n = 2 *p;n <= b;n += p)
          ret.clear(n);

    return ret;
  }
}

class FastFourierTransform{
  static void fft(double[] a,double[] b,boolean invert){
    int count = a.length;
    for (int i = 1,j = 0;i < count;i++) {
      int bit = count >>1;
      for (;j >= bit;bit >>= 1)
        j -= bit;
      j += bit;
      if (i < j) {
        double temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        temp = b[i];
        b[i] = b[j];
        b[j] = temp;
      }
    }
    for (int len = 2;len <= count;len <<= 1) {
      int halfLen = len >>1;
      double angle = 2 *Math.PI /len;
      if (invert)
        angle = -angle;
      double wLenA = Math.cos(angle);
      double wLenB = Math.sin(angle);
      for (int i = 0;i < count;i += len) {
        double wA = 1;
        double wB = 0;
        for (int j = 0;j < halfLen;j++) {
          double uA = a[i +j];
          double uB = b[i +j];
          double vA = a[i +j +halfLen] *wA -b[i +j +halfLen] *wB;
          double vB = a[i +j +halfLen] *wB +b[i +j +halfLen] *wA;
          a[i +j] = uA +vA;
          b[i +j] = uB +vB;
          a[i +j +halfLen] = uA -vA;
          b[i +j +halfLen] = uB -vB;
          double nextWA = wA *wLenA -wB *wLenB;
          wB = wA *wLenB +wB *wLenA;
          wA = nextWA;
        }
      }
    }
    if (invert)
      for (int i = 0;i < count;i++) {
        a[i] /= count;
        b[i] /= count;
      }
  }

  static long[] multiply(long[] a,long[] b){
    int resultSize = Integer.highestOneBit(Math.max(a.length,b.length) -1) <<2;
    resultSize = Math.max(resultSize,1);
    double[] aReal = new double[resultSize];
    double[] aImaginary = new double[resultSize];
    double[] bReal = new double[resultSize];
    double[] bImaginary = new double[resultSize];
    for (int i = 0;i < a.length;i++)
      aReal[i] = a[i];
    for (int i = 0;i < b.length;i++)
      bReal[i] = b[i];
    fft(aReal,aImaginary,false);
    if (a == b) {
      System.arraycopy(aReal,0,bReal,0,aReal.length);
      System.arraycopy(aImaginary,0,bImaginary,0,aImaginary.length);
    } else
      fft(bReal,bImaginary,false);
    for (int i = 0;i < resultSize;i++) {
      double real = aReal[i] *bReal[i] -aImaginary[i] *bImaginary[i];
      aImaginary[i] = aImaginary[i] *bReal[i] +bImaginary[i] *aReal[i];
      aReal[i] = real;
    }
    fft(aReal,aImaginary,true);
    long[] result = new long[resultSize];
    for (int i = 0;i < resultSize;i++)
      result[i] = Math.round(aReal[i]);
    return result;
  }

}

class Edge{
  int id;
  int u;
  int v;
  long l;
  Edge rev;

  Edge(int id,int u,int v){
    this.id = id;
    this.u = u;
    this.v = v;
  }

  void rev(Edge rev){ rev.l = l; }

}

class MyReader{
  byte[] buf = new byte[1 <<16];
  int ptr = 0;
  int tail = 0;
  InputStream in;

  MyReader(InputStream in){ this.in = in; }

  byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  boolean isPrintable(byte c){ return 32 < c && c < 127; }

  boolean isNum(byte c){ return 47 < c && c < 58; }

  byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  int[] arrI(int N,IntUnaryOperator f){
    int[] ret = new int[N];
    setAll(ret,f);
    return ret;
  }

  long[] arrL(int N,IntToLongFunction f){
    long[] ret = new long[N];
    setAll(ret,f);
    return ret;
  }

  double[] arrD(int N,IntToDoubleFunction f){
    double[] ret = new double[N];
    setAll(ret,f);
    return ret;
  }

  <T> T[] arr(T[] arr,IntFunction<T> f){
    setAll(arr,f);
    return arr;
  }

  int it(){ return toIntExact(lg()); }

  int[] it(int N){ return arrI(N,i -> it()); }

  int[][] it(int H,int W){ return arr(new int[H][],i -> it(W)); }

  int idx(){ return it() -1; }

  int[] idx(int N){ return arrI(N,i -> idx()); }

  int[][] idx(int H,int W){ return arr(new int[H][],i -> idx(W)); }

  int[][] qry(int Q){ return arr(new int[Q][],i -> new int[]{idx(), idx(), i}); }

  long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  long[] lg(int N){ return arrL(N,i -> lg()); }

  long[][] lg(int H,int W){ return arr(new long[H][],i -> lg(W)); }

  double dbl(){ return Double.parseDouble(str()); }

  double[] dbl(int N){ return arrD(N,i -> dbl()); }

  double[][] dbl(int H,int W){ return arr(new double[H][],i -> dbl(W)); }

  char[] ch(){ return str().toCharArray(); }

  char[][] ch(int H){ return arr(new char[H][],i -> ch()); }

  String line(){
    StringBuilder sb = new StringBuilder();

    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());

    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  String[] str(int N){ return arr(new String[N],i -> str()); }

  Edge[] e(int N,int M){ return e(N,M,e -> e.l = 1); }

  Edge[] e(int N,int M,Consumer<Edge> f){
    return arr(new Edge[M],i -> {
      Edge e = new Edge(i,idx(),idx());
      f.accept(e);
      return e;
    });
  }

  Edge[][] g(int N,int M,boolean b){ return g(N,b,e(N,M)); }

  Edge[][] g(int N,int M,boolean b,Consumer<Edge> f){ return g(N,b,e(N,M,f)); }

  Edge[][] g(int N,boolean b,Edge[] E){
    int[] c = new int[N];

    for (Edge e:E) {
      c[e.u]++;
      if (!b)
        c[e.v]++;
    }

    Edge[][] g = arr(new Edge[N][],i -> new Edge[c[i]]);

    for (Edge e:E) {

      g[e.u][--c[e.u]] = e;
      if (!b) {
        Edge rev = new Edge(e.id,e.v,e.u);
        e.rev(rev);
        g[e.v][--c[e.v]] = e.rev = rev;
      }
    }
    return g;
  }
}

class MyWriter{
  OutputStream out;
  byte[] buf = new byte[1 <<16];
  byte[] ibuf = new byte[20];
  int tail = 0;

  MyWriter(OutputStream out){ this.out = out; }

  void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  protected void ln(){ write((byte) '\n'); }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(byte[] b,int off,int len){
    for (int i = off;i < off +len;i++)
      write(b[i]);
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }

    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);

    write(ibuf,i,ibuf.length -i);
  }

  private void print(Object obj){
    if (obj instanceof Boolean)
      print((boolean) obj ? Solver.yes : Solver.no);
    else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++) {
        print(Array.get(obj,i));
        if (i +1 < l)
          write((byte) ' ');
      }
    } else if (obj instanceof Character)
      write((byte) (char) obj);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[])
      for (char b:(char[]) obj)
        write((byte) b);
    else
      for (char b:Objects.toString(obj).toCharArray())
        write((byte) b);
  }

  void println(Object obj){
    if (obj == null)
      return;

    if (obj instanceof Collection<?>)
      for (var e:(Collection<?>) obj)
        println(e);
    else if (obj.getClass().isArray()
        && !(Array.get(obj,0) instanceof char[])
        && Array.get(obj,0).getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++)
        println(Array.get(obj,i));
    } else {
      print(obj);
      ln();
    }
  }
}

class Main{
  public static void main(String[] args) throws Exception{
    Solver solver = new Solver();
    Optional.ofNullable(solver.solve()).ifPresent(solver.out::println);
    solver.out.flush();
    solver.log.println(solver.elapsed());
  }
}

yukicoder

結果

テストケース

ソースコード