#935443 (Java21) No.2570 最大最大公約数

提出ソース
結果

問題	No.2570 最大最大公約数
ユーザー	ゆうき
提出日時	2023-12-02 17:12:20
言語	Java21 (openjdk 21)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	17,814 bytes
コンパイル時間	8,084 ms
コンパイル使用メモリ	97,676 KB
実行使用メモリ	148,596 KB
最終ジャッジ日時	2024-11-13 17:15:55
合計ジャッジ時間	23,491 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	AC	903 ms 106,336 KB
testcase_02	AC	1,321 ms 111,060 KB
testcase_03	AC	1,357 ms 107,136 KB
testcase_04	AC	832 ms 106,928 KB
testcase_05	AC	950 ms 97,336 KB
testcase_06	AC	1,502 ms 113,728 KB
testcase_07	AC	1,738 ms 134,920 KB
testcase_08	AC	618 ms 93,124 KB
testcase_09	AC	653 ms 94,248 KB
testcase_10	AC	1,949 ms 137,784 KB
testcase_11	AC	1,973 ms 148,596 KB
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	AC	1,431 ms 112,676 KB
testcase_16	AC	1,403 ms 113,200 KB
testcase_17	AC	932 ms 105,652 KB
testcase_18	AC	308 ms 94,380 KB
testcase_19	AC	347 ms 95,260 KB
testcase_20	AC	318 ms 95,096 KB
testcase_21	AC	350 ms 95,036 KB
testcase_22	AC	347 ms 95,440 KB
testcase_23	AC	353 ms 95,484 KB
testcase_24	AC	332 ms 95,168 KB
testcase_25	AC	423 ms 97,292 KB
testcase_26	AC	419 ms 97,480 KB
testcase_27	AC	362 ms 95,640 KB
testcase_28	AC	339 ms 95,288 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import static java.lang.Math.*;
import static java.util.Arrays.*;

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

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

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

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

  static int infI = (1 <<30) -1;
  static long infL = 1L <<60;
  //static long mod = (int) 1e9 +7;
  static long mod = 998244353;
  static String yes = "Yes";
  static String no = "No";

  static Random rd = ThreadLocalRandom.current();
  MyReader in = new MyReader(System.in);
  MyWriter out = new MyWriter(System.out);
  MyWriter log = new MyWriter(System.err){
    @Override
    void println(Object obj){ super.println(obj == null ? "null" : obj); };

    @Override
    protected void ln(){
      super.ln();
      flush();
    };
  };

  Object solve(){
    int N = in.it();
    int K = in.it();
    long[] A = in.lg(N);
    var pm = new Prime();
    TreeSet<Long>divs = new TreeSet<>();
    for(var a:A)
      for(int k = -K;k<=K;k++)
      if(1<a+k)
      for(var d:pm.divisors(a+k))
        divs.add(d);

    while(!divs.isEmpty()){
      long gcd = divs.pollLast();
      long cost = 0;
      for(var a:A){
        long l = a/gcd*gcd;
        long r = l+gcd;
        cost+=min(a-l,r-a);
        if(K<cost)
          break;
      }
      if(cost<=K)
      return gcd;
    }
      
    return 1;
  }
  long ceil(long a,long b){return (a+b-1)/b;}

  private long pow(long x,long n,long mod){
    long ret = 1;
    for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
      if ((n &1) == 1)
        ret = ret *x %mod;
    return ret;
  }

}
class Prime{
  private Random rd = ThreadLocalRandom.current();
  private int[] spf;
  private long[] AInt;
  private BigInteger[] ALng;

  Prime(){ this(10_000_000); }

  Prime(int n){
    spf = Util.arrI(n +1,i -> i);
    for (int p = 2;p *p <= n;p++)
      if (spf[p] == p)
        for (int l = p *p;l <= n;l += p)
          spf[l] = p;
    AInt = new long[]{2, 7, 61};
    ALng = IntStream.of(2,325,9375,28178,450775,9780504,1795265022)
        .mapToObj(BigInteger::valueOf)
        .toArray(l -> new BigInteger[l]);
  }

  boolean isPrime(long n){
    if (n < spf.length)
      return 1 < n && spf[(int) n] == n;
    if ((n &1) == 0)
      return false;
    long lsb = Long.lowestOneBit(n -1);
    if (n < 1 <<30) {
      long m = (n -1) /lsb;
      a:for (var a:AInt) {
        long z = pow(a,m,n);
        if (z < 2)
          continue;
        for (long k = 1;k <= lsb;k <<= 1)
          if (z == n -1)
            continue a;
          else
            z = z *z %n;
        return false;
      }
    } else {
      BigInteger bn = BigInteger.valueOf(n),m = BigInteger.valueOf((n -1) /lsb);
      a:for (var ba:ALng) {
        var z = ba.modPow(m,bn);
        if (z.longValue() < 2)
          continue;
        for (long k = 1;k <= lsb;k <<= 1)
          if (z.longValue() == n -1)
            continue a;
          else
            z = z.multiply(z).mod(bn);
        return false;
      }
    }
    return true;
  }

  long[] factorize(long n){
    if (n < 2)
      return new long[0];
    long[] ret = new long[64];
    int h = 0,t = 0;
    ret[t++] = n;
    while (h < t) {
      long cur = ret[h++];
      if (!isPrime(cur)) {
        var p = rho(cur);
        ret[--h] = p;
        ret[t++] = cur /p;
      }
    }
    sort(ret,0,t);
    return copyOf(ret,t);
  }

  long[] divisors(long n){
    long[] fs = factorize(n);
    int l = 2,id = 0;
    for (int i = 1,sz = 1;i < fs.length;i++,l += sz)
      if (fs[i -1] < fs[i])
        sz = l;

    long[] ret = new long[l];
    ret[id++] = 1;
    ret[id++] = fs[0];
    for (int i = 1,s = 0,sz = 1;i < fs.length;i++,s += sz) {
      if (fs[i -1] < fs[i]) {
        sz = id;
        s = 0;
      }
      for (int j = s;j < s +sz;j++)
        ret[id++] = ret[j] *fs[i];
    }
    return ret;
  }

  private long rho(long n){
    if (n < spf.length)
      return spf[(int) n];
    if (n %2 == 0)
      return 2;
    BigInteger bn = BigInteger.valueOf(n);
    for (long t;;) {
      long x = 0,y = x,q = 1,c = rd.nextLong(n -1) +1;
      a:for (int k = 1;;k <<= 1,y = x,q = 1)
        for (int i = k;i-- > 0;) {
          x = mul(x,x,bn) +c;
          if (n <= x)
            x -= n;
          q = mul(q,Math.abs(x -y),bn);
          if ((i &127) == 0 && (t = gcd(q,n)) > 1)
            break a;
        }
      if (t < n)
        return t;
    }
  }

  public long mul(long a,long b,BigInteger bn){
    return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(bn).longValue();
  }

  private long pow(long x,long n,long mod){
    long ret = 1;
    for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
      if ((n &1) == 1)
        ret = ret *x %mod;
    return ret;
  }

  private long gcd(long a,long b){
    while (0 < b) {
      long t = a;
      a = b;
      b = t %b;
    }
    return a;
  }
}

abstract class Seg<V, F> {
  protected int n,log;
  private V[] val;
  private F[] lazy;
  private int[] l,r;

  @SuppressWarnings("unchecked")
  Seg(int n){
    this.n = n;
    while (1 <<log <= n)
      log++;
    val = (V[]) new Object[n <<1];
    lazy = (F[]) new Object[n];
    l = new int[n <<1];
    r = new int[n <<1];

    for (int i = -1;++i < n;l[i +n] = i,r[i +n] = i +1)
      val[i +n] = init(i);
    for (int i = n;--i > 0;l[i] = l[i <<1],r[i] = r[i <<1 |1])
      merge(i);
  }

  protected V init(int i){ return e(); }

  abstract V e();

  abstract V agg(V v0,V v1);

  abstract V map(V v,F f,int l,int r);

  abstract F comp(F f0,F f1);

  protected V eval(int i){
    if (i < n && lazy[i] != null) {
      rangeMap(i);
      prop(i <<1,lazy[i]);
      prop(i <<1 |1,lazy[i]);
      lazy[i] = null;
    }
    return val[i];
  }

  private void merge(int i){ val[i] = agg(eval(i <<1),eval(i <<1 |1)); }

  protected void rangeMap(int i){ val[i] = map(val[i],lazy[i],l[i],r[i]); }

  protected void prop(int i,F f){
    if (i < n)
      lazy[i] = lazy[i] == null ? f : comp(lazy[i],f);
    else
      val[i] = map(val[i],f,l[i],r[i]);
  }

  protected void up(int l,int r){
    l = oddPart(l +n);
    r = oddPart(r +n);
    while (1 < l)
      merge(l >>= 1);
    while (1 < r)
      merge(r >>= 1);
  }

  protected void down(int l,int r){
    l = oddPart(l +n);
    r = oddPart(r +n);
    for (int i = log;i > 0;i--) {
      if (l >>i > 0)
        eval(l >>i);
      if (r >>i > 0)
        eval(r >>i);
    }
  }

  private int oddPart(int i){ return i /(i &-i); }

  protected void upd(int i,F f){ prop(i +n,f); }

  protected void upd(int l,int r,F f){
    l += n;
    r += n;
    do {
      if ((l &1) == 1)
        prop(l++,f);
      if ((r &1) == 1)
        prop(--r,f);
    } while ((l >>= 1) < (r >>= 1));
  }

  protected V get(int i){ return val[i +n]; }

  protected V get(int l,int r){
    l += n;
    r += n;
    V vl = e(),vr = e();
    do {
      vl = (l &1) == 0 ? vl : agg(vl,eval(l++));
      vr = (r &1) == 0 ? vr : agg(eval(--r),vr);
    } while ((l >>= 1) < (r >>= 1));

    return agg(vl,vr);
  }

}

abstract class SegmentTree<V, F> extends Seg<V, F>{

  SegmentTree(int n){ super(n); }

  @Override
  protected F comp(F f0,F f1){ return null; }

  @Override
  protected void upd(int i,F f){
    super.upd(i,f);
    up(i,i +1);
  }

}

class DeletablePque<T> {
  private Queue<T> que,rem;
  private Comparator<T> cmp;

  @SuppressWarnings("unchecked")
  public DeletablePque(){ this((Comparator<T>) Comparator.naturalOrder()); }

  public <U extends Comparable<U>> DeletablePque(Function<T, U> func){ this(Comparator.comparing(func)); }

  private DeletablePque(Comparator<T> cmp){
    this.cmp = cmp;
    que = new PriorityQueue<>(cmp);
    rem = new PriorityQueue<>(cmp);
  }

  public boolean add(T t){ return que.add(t); }

  public boolean remove(T t){ return rem.add(t); }

  public T poll(){ return adj().poll(); }

  public T peek(){ return adj().peek(); }

  private Queue<T> adj(){
    while (!que.isEmpty() && !rem.isEmpty()
        && cmp.compare(que.peek(),rem.peek()) == 0) {
      que.poll();
      rem.poll();
    }
    return que;
  }
}

class Mex{
  private int[] cnt;
  private DeletablePque<Integer> que;
  private Queue<Integer> wait;
  private int add;

  public Mex(){ this(16); }

  public Mex(int n){
    cnt = new int[n];
    que = new DeletablePque<>();
    wait = new PriorityQueue<>();
    for (int x = 0;x < cnt.length;x++)
      que.add(x);
  }

  public int add(int x){
    if (++add == cnt.length)
      grow();
    if (x < cnt.length) {
      if (cnt[x]++ == 0)
        que.remove(x);
    } else
      wait.add(x);
    return que.peek();
  }

  public int remove(int x){
    if (x < cnt.length && --cnt[x] == 0)
      que.add(x);
    return que.peek();
  }

  private void grow(){
    for (int x = cnt.length;x < cnt.length <<1;x++)
      que.add(x);
    for (cnt = copyOf(cnt,cnt.length <<1);!wait.isEmpty() && wait.peek() < cnt.length;add--)
      add(wait.poll());
  }

}

abstract class Dijkstra<E, L> extends Graph<E>{
  protected L[] len;
  private int[] arr,rev;
  private int sz;
  protected Edge<E>[] pre;
  private Comparator<L> cmp;
  protected L zero,inf;

  @SuppressWarnings("unchecked")
  public Dijkstra(int n,boolean dir){ this(n,dir,(Comparator<L>) Comparator.naturalOrder()); }

  public <U extends Comparable<U>> Dijkstra(int n,boolean dir,Function<L, U> func){
    this(n,dir,Comparator.comparing(func));
  }

  @SuppressWarnings("unchecked")
  public Dijkstra(int n,boolean dir,Comparator<L> cmp){
    super(n,dir);
    this.cmp = cmp;
    zero = zero();
    inf = inf();
    len = (L[]) new Object[n];
    arr = new int[n];
    rev = new int[n];
    pre = new Edge[n];
  }

  protected abstract L zero();

  protected abstract L inf();

  protected abstract L f(L l,E val);

  public void calcFrom(int s){ calc(s,-1); }

  public void calc(int s,int g){
    init();
    pre[s] = null;
    set(s,zero);
    while (!isEmpty()) {
      var cur = poll();
      if (cur == g)
        break;
      L l = len[cur];
      for (var e:go(cur)) {
        L ll = f(l,e.val);
        if (cmp.compare(ll,len[e.v]) < 0) {
          pre[e.v] = e;
          set(e.v,ll);
        }
      }
    }
  }

  public L len(int t){ return len[t]; }

  public Deque<Edge<E>> path(int t){
    Deque<Edge<E>> ret = new ArrayDeque<>();
    while (pre[t] != null) {
      ret.addFirst(pre[t]);
      t = pre[t].u;
    }

    return ret;
  }

  private void init(){
    fill(len,inf);
    setAll(arr,i -> i);
    setAll(rev,i -> i);
    sz = n;
  }

  private boolean isEmpty(){ return sz == 0; }

  private void set(int i,L l){
    if (sz <= rev[i] || cmp.compare(len[i],l) <= 0)
      return;
    len[i] = l;
    heapfy(rev[i]);
  }

  private int poll(){
    int ret = arr[0];
    heapfy(swap(0,--sz));
    return ret;
  }

  private void heapfy(int k){
    int p = k -1 >>1;
    if (0 <= p && cmp.compare(len[arr[p]],len[arr[k]]) > 0) {
      heapfy(swap(p,k));
      return;
    }

    int c = k <<1 |1;
    if (sz <= c)
      return;

    if (c +1 < sz && cmp.compare(len[arr[c +1]],len[arr[c]]) < 0)
      c++;

    if (cmp.compare(len[arr[c]],len[arr[k]]) < 0)
      heapfy(swap(c,k));
  }

  private int swap(int i,int j){
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    rev[arr[i]] = i;
    rev[arr[j]] = j;
    return i;
  }
}

class Edge<L> {
  int id,u,v;
  L val;
  Edge<L> re;

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

  @Override
  public String toString(){ return "(" +u +"," +v +"," +val +")"; }
}

class UnionFind{
  int num;
  int[] dat;
  int[] nxt;
  long[]val;

  public UnionFind(int n,long[] val){
    dat = new int[n];
    nxt = new int[n];
    setAll(nxt,i -> i);
    fill(dat,-1);
    num = n;
    this.val = val;
  }

  int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }

  boolean same(int u,int v){ return root(u) == root(v); }

  boolean unite(int u,int v){
    if ((u = root(u)) == (v = root(v)))
      return false;

    if (dat[u] > dat[v]) {
      u ^= v;
      v ^= u;
      u ^= v;
    }
    dat[u] += dat[v];
    val[u] += val[v];
    dat[v] = u;
    num--;
    nxt[u] ^= nxt[v];
    nxt[v] ^= nxt[u];
    nxt[u] ^= nxt[v];
    return true;
  }

  int size(int x){ return -dat[root(x)]; }

  int[] getGroup(int x){
    int[] ret = new int[size(x)];
    for (int i = 0,c = root(x);i < ret.length;i++)
      ret[i] = c = nxt[c];
    return ret;
  }

}

class Graph<L> {
  public int n;
  List<Edge<L>> es;
  private List<Edge<L>>[] go,bk;

  @SuppressWarnings("unchecked")
  public Graph(int n,boolean dir){
    this.n = n;
    go = new List[n];
    bk = dir ? new List[n] : go;
    for (int i = 0;i < n;i++) {
      go[i] = new ArrayList<>();
      bk[i] = new ArrayList<>();
    }
    es = new ArrayList<>();
  }

  public void addEdge(int u,int v){ addEdge(u,v,null); }

  public void addEdge(int u,int v,L l){
    var e = new Edge<>(es.size(),u,v,l);
    var re = new Edge<>(e.id,e.v,e.u,inv(e.val));
    es.add(e);
    go[u].add(re.re = e);
    bk[v].add(e.re = re);
  }

  protected L inv(L l){ return l; }

  public List<Edge<L>> go(int ui){ return go[ui]; }

  public List<Edge<L>> back(int ui){ return bk[ui]; }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  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 Util.arrL(N,i -> lg()); }

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

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

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

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

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

  char[][] ch(int H){ return Util.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 Util.arr(new String[N],i -> str()); }
}

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

  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 instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[] cs)
      for (char b:cs)
        write((byte) b);
    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
      print(Objects.toString(obj).toCharArray());
  }

  void println(Object obj){
    if (obj == null)
      return;
    if (obj instanceof Iterable<?> co)
      for (Object e:co)
        println(e);
    else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && 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();
    }
  }

  void printlns(Object... o){
    print(o);
    ln();
  }
}

class Main{
  public static void main(String[] args) throws Exception{
    new Solver(){
      public void exe(){
        out.println(solve());
        out.flush();
        log.println(elapsed());
      }
    }.exe();
  }
}
yukicoder

結果

テストケース

ソースコード
