結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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

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