結果
問題 | No.2570 最大最大公約数 |
ユーザー |
|
提出日時 | 2023-12-02 17:12:20 |
言語 | Java (openjdk 23) |
結果 |
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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 TLE * 4 |
ソースコード
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){@Overridevoid println(Object obj){ super.println(obj == null ? "null" : obj); };@Overrideprotected 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;elsez = 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;elsez = 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);elseval[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); }@Overrideprotected F comp(F f0,F f1){ return null; }@Overrideprotected 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);} elsewait.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;}@Overridepublic 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) ' ');}} elseprint(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();}}