結果
| 問題 | No.1036 Make One With GCD 2 |
| ユーザー |
 shun_skycrew
|
| 提出日時 | 2022-09-22 13:22:56 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 626 ms / 2,000 ms |
| コード長 | 36,334 bytes |
| コンパイル時間 | 4,499 ms |
| コンパイル使用メモリ | 95,592 KB |
| 実行使用メモリ | 53,504 KB |
| 最終ジャッジ日時 | 2024-12-22 04:50:29 |
| 合計ジャッジ時間 | 22,897 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 41 |
ソースコード
import java.util.*;import java.io.*;import java.util.function.*;final class FastInputStream {private static final int BUF_SIZE = 1 << 14;private final InputStream in;private final byte buf[] = new byte[BUF_SIZE];private int pos = 0;private int count = 0;private static final int TOKEN_SIZE = 1 << 20;private final byte tokenBuf[] = new byte[TOKEN_SIZE];public FastInputStream(final InputStream in) {this.in = in;}private final void readBuf() {pos = 0;try { count = in.read(buf); }catch(IOException e) { e.printStackTrace(); }}private final boolean hasNextByte() {if(pos < count) return true;readBuf();return count > 0;}private final byte read() { if(hasNextByte()) return buf[pos ++]; else throw new NoSuchElementException(); }private final boolean isPrintableChar(final byte c) { return 33 <= c && c <= 126; }private final boolean isNumber(final byte c) { return 48 <= c && c <= 57; }private final void skipUnprintable() {while(true) {for(int i = pos; i < count; i ++) {if(isPrintableChar(buf[i])) { pos = i; return; }}readBuf();if(count <= 0) throw new NoSuchElementException();}}private final boolean readEOL() {if(!hasNextByte()) return true;if(buf[pos] == 13) {pos ++;if(hasNextByte() && buf[pos] == 10) pos ++;return true;}if(buf[pos] == 10) {pos ++;return true;}return false;}public final char nextChar() {skipUnprintable();return (char)buf[pos ++];}public final String next() {skipUnprintable();int tokenCount = 0;outer: while(count > 0) {for(int i = pos; i < count; i ++) {final byte b = buf[i];if(!isPrintableChar(b)) { pos = i; break outer; }tokenBuf[tokenCount ++] = b;}readBuf();}return new String(tokenBuf, 0, tokenCount);}public final String nextLine() {readEOL();if(!hasNextByte()) throw new NoSuchElementException();int tokenCount = 0;while(!readEOL()) tokenBuf[tokenCount ++] = read();return new String(tokenBuf, 0, tokenCount);}public final int nextInt() {skipUnprintable();int n = 0;boolean minus = false;if(buf[pos] == 45) {minus = true;pos ++;if(!hasNextByte() || !isNumber(buf[pos])) throw new InputMismatchException();}outer: while(count > 0) {for(int i = pos; i < count; i ++) {final byte b = buf[i];if(!isPrintableChar(b)) { pos = i; break outer; }if(!isNumber(b)) throw new InputMismatchException();if(minus) {if(n < - 214748364) throw new ArithmeticException("int overflow");if(n == - 214748364 && b > 56) throw new ArithmeticException("int overflow");n = (n << 3) + (n << 1) + 48 - b;}else {if(n > 214748364) throw new ArithmeticException("int overflow");if(n == 214748364 && b >= 56) throw new ArithmeticException("int overflow");n = (n << 3) + (n << 1) - 48 + b;}}readBuf();}return n;}public final long nextLong() {skipUnprintable();long n = 0;boolean minus = false;if(buf[pos] == 45) {minus = true;pos ++;if(!hasNextByte() || !isNumber(buf[pos])) throw new InputMismatchException();}outer: while(count > 0) {for(int i = pos; i < count; i ++) {final byte b = buf[i];if(!isPrintableChar(b)) { pos = i; break outer; }if(!isNumber(b)) throw new InputMismatchException();if(minus) {if(n < - 922337203685477580l) throw new ArithmeticException("long overflow");if(n == - 922337203685477580l && b > 56) throw new ArithmeticException("long overflow");n = (n << 3) + (n << 1) + 48 - b;}else {if(n > 922337203685477580l) throw new ArithmeticException("long overflow");if(n == 922337203685477580l && b >= 56) throw new ArithmeticException("long overflow");n = (n << 3) + (n << 1) - 48 + b;}}readBuf();}return n;}public final double nextDouble() { return Double.parseDouble(next()); }public final void close() {try { in.close(); }catch(IOException e) { e.printStackTrace(); }}}final class FastOutputStream {private static final int BUF_SIZE = 1 << 13;private final byte buf[] = new byte[BUF_SIZE];private final OutputStream out;private int count = 0;private static final byte TRUE_BYTES[] = {116, 114, 117, 101};private static final byte FALSE_BYTES[] = {102, 97, 108, 115, 101};private static final byte INT_MIN_BYTES[] = {45, 50, 49, 52, 55, 52, 56, 51, 54, 52, 56};private static final byte LONG_MIN_BYTES[] = {45, 57, 50, 50, 51, 51, 55, 50, 48, 51,54, 56, 53, 52, 55, 55, 53, 56, 48, 56};private static final int TOKEN_SIZE = 20;private final byte tokenBuf[] = new byte[TOKEN_SIZE];private static final int PRECISION = 10;public FastOutputStream(OutputStream out) {this.out = out;}public final void print() { }public final void write(final byte b) {if(count == BUF_SIZE) internalFlush();buf[count ++] = b;}public final void print(final char c) { write((byte) c); }public final void print(final boolean b) {if(b) {if(count + 4 > BUF_SIZE) internalFlush();System.arraycopy(TRUE_BYTES, 0, buf, count, TRUE_BYTES.length);count += TRUE_BYTES.length;}else {if(count + 5 > BUF_SIZE) internalFlush();System.arraycopy(FALSE_BYTES, 0, buf, count, FALSE_BYTES.length);count += FALSE_BYTES.length;}}public final void print(int x) {if(count + 11 > BUF_SIZE) internalFlush();if(x == Integer.MIN_VALUE) {System.arraycopy(INT_MIN_BYTES, 0, buf, count, INT_MIN_BYTES.length);count += INT_MIN_BYTES.length;return;}if(x == 0) {buf[count ++] = 48;return;}if(x < 0) {buf[count ++] = 45;x = - x;}int tokenCount = 11;while(x > 0) {final int y = x / 10;tokenBuf[-- tokenCount] = (byte) (x - (y << 3) - (y << 1) + 48);x = y;}System.arraycopy(tokenBuf, tokenCount, buf, count, 11 - tokenCount);count += 11 - tokenCount;}public final void print(long x) {if(count + 20 > BUF_SIZE) internalFlush();if(x == Long.MIN_VALUE) {System.arraycopy(LONG_MIN_BYTES, 0, buf, count, LONG_MIN_BYTES.length);count += LONG_MIN_BYTES.length;return;}if(x == 0) {buf[count ++] = 48;return;}if(x < 0) {buf[count ++] = 45;x = - x;}int tokenCount = 20;while(x > 0) {final long y = x / 10;tokenBuf[-- tokenCount] = (byte) (x - (y << 3) - (y << 1) + 48);x = y;}System.arraycopy(tokenBuf, tokenCount, buf, count, 20 - tokenCount);count += 20 - tokenCount;}public final void print(final double d) { print(d, PRECISION); }public final void print(double d, final int precision) {if(count == BUF_SIZE) internalFlush();if(d < 0) {buf[count ++] = 45;d = - d;}d += Math.pow(10, - precision) / 2;print((long)d);if(precision == 0) return;if(count + precision + 1 > BUF_SIZE) internalFlush();buf[count ++] = 46;d -= (long)d;for(int i = 0; i < precision; i ++) {d *= 10;buf[count ++] = (byte)((int)d + 48);d -= (int) d;}}public final void print(final String s) { print(s.getBytes()); }public final void print(final Object o) { print(o.toString()); }public final void print(final byte[] a) {if(count + a.length > BUF_SIZE) internalFlush();System.arraycopy(a, 0, buf, count, a.length);count += a.length;}public final void print(final char[] a) {if(count + a.length > BUF_SIZE) internalFlush();for(int i = 0; i < a.length; i ++) buf[count + i] = (byte)a[i];count += a.length;}public final void println() { print('\n'); }public final void println(final char c) { print(c); println(); }public final void println(final boolean b) { print(b); println(); }public final void println(final int x) { print(x); println(); }public final void println(final long x) { print(x); println(); }public final void println(final double d) { print(d); println(); }public final void println(final double d, final int precision) { print(d, precision); println(); }public final void println(final String s) { print(s); println(); }public final void println(final Object o) { print(o); println(); }public final void println(final char[] a) { print(a); println(); }public final void println(final int[] a) {for(int i = 0; i < a.length; i ++) {print(a[i]);print(i == a.length - 1 ? '\n' : ' ');}}public final void println(final long[] a) {for(int i = 0; i < a.length; i ++) {print(a[i]);print(i == a.length - 1 ? '\n' : ' ');}}public final void println(final double[] a) {for(int i = 0; i < a.length; i ++) {print(a[i]);print(i == a.length - 1 ? '\n' : ' ');}}public final void println(final double[] a, final int precision) {for(int i = 0; i < a.length; i ++) {print(a[i], precision);print(i == a.length - 1 ? '\n' : ' ');}}public final void println(final String[] a) {for(int i = 0; i < a.length; i ++) {print(a[i]);print(i == a.length - 1 ? '\n' : ' ');}}public final void println(final Object[] a) {for(int i = 0; i < a.length; i ++) {print(a[i]);print(i == a.length - 1 ? '\n' : ' ');}}private final void internalFlush() {try {out.write(buf, 0, count);count = 0;}catch(IOException e) { e.printStackTrace(); }}public final void flush() {try {out.write(buf, 0, count);out.flush();count = 0;}catch(IOException e) { e.printStackTrace(); }}public final void close() {try { out.close(); }catch(IOException e) { e.printStackTrace(); }}}class SimpleUtil {public static boolean DEBUG;private static final FastInputStream in = new FastInputStream(System.in);public static final String nline() { return in.nextLine(); }public static final String[] nline(final int n) { final String a[] = new String[n]; for(int i = 0; i < n; i ++) a[i] = nline(); return a; }public static final char nc() { return in.nextChar(); }public static final char[] nc(int n) {final String str = nline();if(n < 0) n = str.length();final char a[] = new char[n];for(int i = 0; i < n; i ++) a[i] = str.charAt(i);return a;}public static final char[][] nc(final int n, final int m) { final char a[][] = new char[n][m]; for(int i = 0; i < n; i ++) a[i] = nc(m); return a; }public static final boolean[] nb(int n, final char t) {final char c[] = nc(-1);if(n < 0) n = c.length;final boolean a[] = new boolean[n];for(int i = 0; i < n; i ++) a[i] = c[i] == t;return a;}public static final boolean[][] nb(final int n, final int m, final char t) { final boolean a[][] = new boolean[n][]; for(int i = 0; i < n; i ++)a[i] = nb(m, t); return a; }public static final int ni() { return in.nextInt(); }public static final int[] ni(final int n) { final int a[] = new int[n]; for(int i = 0; i < n; i ++) a[i] = ni(); return a; }public static final int[][] ni(final int n, final int m) { final int a[][] = new int[n][]; for(int i = 0; i < n; i ++) a[i] = ni(m); return a; }public static final long nl() { return in.nextLong(); }public static final long[] nl(final int n) { final long a[] = new long[n]; for(int i = 0; i < n; i ++) a[i] = nl(); return a; }public static final long[][] nl(final int n, final int m) { final long a[][] = new long[n][]; for(int i = 0; i < n; i ++) a[i] = nl(m); return a;}public static final double nd() { return in.nextDouble(); }public static final double[] nd(final int n) { final double a[] = new double[n]; for(int i = 0; i < n; i ++) a[i] = nd(); return a; }public static final double[][] nd(final int n, final int m) { final double a[][] = new double[n][]; for(int i = 0; i < n; i ++) a[i] = nd(m);return a; }public static final String ns() { return in.next(); }public static final String[] ns(final int n) { final String a[] = new String[n]; for(int i = 0; i < n; i ++) a[i] = ns(); return a; }public static final String[][] ns(final int n, final int m) { final String a[][] = new String[n][]; for(int i = 0; i < n; i ++) a[i] = ns(m);return a; }private static final FastOutputStream out = new FastOutputStream(System.out);private static final FastOutputStream err = new FastOutputStream(System.err);public static final void prt() { out.print(); }public static final void prt(final char c) { out.print(c); }public static final void prt(final boolean b) { out.print(b); }public static final void prt(final int x) { out.print(x); }public static final void prt(final long x) { out.print(x); }public static final void prt(final double d) { out.print(d); }public static final void prt(final String s) { out.print(s); }public static final void prt(final Object o) { out.print(o); }public static final void prtln() { out.println(); }public static final void prtln(final char c) { out.println(c); }public static final void prtln(final boolean b) { out.println(b); }public static final void prtln(final int x) { out.println(x); }public static final void prtln(final long x) { out.println(x); }public static final void prtln(final double d) { out.println(d); }public static final void prtln(final String s) { out.println(s); }public static final void prtln(final Object o) { out.println(o); }public static final void prtln(final char... a) { out.println(a); }public static final void prtln(final boolean... a) { out.println(booleanToChar(a)); }public static final void prtln(final int... a) { out.println(a); }public static final void prtln(final long... a) { out.println(a); }public static final void prtln(final double... a) { out.println(a); }public static final void prtln(final double[] a, int precision) { out.println(a, precision); }public static final void prtln(final String... a) { out.println(a); }public static final void prtln(final Object[] a) { out.println(a); }public static final void prtlns(final char... a) { for(char ele : a) prtln(ele); }public static final void prtlns(final boolean... a) { for(boolean ele : a) prtln(ele); }public static final void prtlns(final int... a) { for(int ele : a) prtln(ele); }public static final void prtlns(final long... a) { for(long ele : a) prtln(ele); }public static final void prtlns(final double... a) { for(double ele : a) prtln(ele); }public static final void prtlns(final Object[] a) { for(Object ele : a) prtln(ele); }public static final void prtln(final char[][] a) { for(char[] ele : a) prtln(ele); }public static final void prtln(final boolean[][] a) { for(boolean[] ele : a) prtln(ele); }public static final void prtln(final int[][] a) { for(int[] ele : a) prtln(ele); }public static final void prtln(final long[][] a) { for(long[] ele : a) prtln(ele); }public static final void prtln(final double[][] a) { for(double[] ele : a) prtln(ele); }public static final void prtln(final double[][] a, int precision) { for(double[] ele : a) prtln(ele, precision); }public static final void prtln(final String[][] a) { for(String[] ele : a) prtln(ele); }public static final void prtln(final Object[][] a) { for(Object[] ele : a) prtln(ele); }public static final void errprt() { if(DEBUG) err.print(); }public static final void errprt(final char c) { if(DEBUG) err.print(c); }public static final void errprt(final boolean b) { if(DEBUG) err.print(booleanToChar(b)); }public static final void errprt(final int x) { if(DEBUG) if(isINF(x)) err.print('_'); else err.print(x); }public static final void errprt(final long x) { if(DEBUG) if(isINF(x)) err.print('_'); else err.print(x); }public static final void errprt(final double d) { if(DEBUG) err.print(d); }public static final void errprt(final String s) { if(DEBUG) err.print(s); }public static final void errprt(final Object o) { if(DEBUG) err.print(o); }public static final void errprtln() { if(DEBUG) err.println(); }public static final void errprtln(final char c) { if(DEBUG) err.println(c); }public static final void errprtln(final boolean b) { if(DEBUG) err.println(booleanToChar(b)); }public static final void errprtln(final int x) { if(DEBUG) if(isINF(x)) err.println('_'); else err.println(x); }public static final void errprtln(final long x) { if(DEBUG) if(isINF(x)) err.println('_'); else err.println(x); }public static final void errprtln(final double d) { if(DEBUG) err.println(d); }public static final void errprtln(final String s) { if(DEBUG) err.println(s); }public static final void errprtln(final Object o) { if(DEBUG) err.println(o); }public static final void errprtln(final char... a) { if(DEBUG) err.println(a); }public static final void errprtln(final boolean... a) { if(DEBUG) err.println(booleanToChar(a)); }public static final void errprtln(final int... a) {if(DEBUG) {boolean start = false;for(int ele : a) {errprt(ele);if(!start) errprt(' ');start = false;}err.println();}}public static final void errprtln(final long... a) {if(DEBUG) {boolean start = false;for(long ele : a) {errprt(ele);if(!start) errprt(' ');start = false;}err.println();}}public static final void errprtln(final double... a) { if(DEBUG) err.println(a); }public static final void errprtln(final double[] a, final int precision) { if(DEBUG) err.println(a, precision); }public static final void errprtln(final String... a) { if(DEBUG) err.println(a); }public static final void errprtln(final Object[] a) { if(DEBUG) err.println(a); }public static final void errprtlns(final char... a) { if(DEBUG) for(char ele : a) errprtln(ele); }public static final void errprtlns(final boolean... a) { if(DEBUG) for(boolean ele : a) errprtln(ele); }public static final void errprtlns(final int... a) { if(DEBUG) for(int ele : a) errprtln(ele); }public static final void errprtlns(final long... a) { if(DEBUG) for(long ele : a) errprtln(ele); }public static final void errprtlns(final double... a) { if(DEBUG) for(double ele : a) errprtln(ele); }public static final void errprtlns(final Object[] a) { if(DEBUG) for(Object ele : a) errprtln(ele); }public static final void errprtln(final char[][] a) { if(DEBUG) for(char[] ele : a) errprtln(ele); }public static final void errprtln(final boolean[][] a) { if(DEBUG) for(boolean[] ele : a) errprtln(ele); }public static final void errprtln(final int[][] a) { if(DEBUG) for(int[] ele : a) errprtln(ele); }public static final void errprtln(final long[][] a) { if(DEBUG) for(long[] ele : a) errprtln(ele); }public static final void errprtln(final double[][] a) { if(DEBUG) for(double[] ele : a) errprtln(ele); }public static final void errprtln(final double[][] a, int precision) { if(DEBUG) for(double[] ele : a) errprtln(ele, precision); }public static final void errprtln(final String[][] a) { if(DEBUG) for(String[] ele : a) errprtln(ele); }public static final void errprtln(final Object[][] a) { if(DEBUG) for(Object[] ele : a) errprtln(ele); }public static final void errprtlns(final Object[][] a) { if(DEBUG) for(Object[] ele : a) { errprtlns(ele); errprtln(); } }public static final void reply(final boolean b) { prtln(b ? "Yes" : "No"); }public static final void REPLY(final boolean b) { prtln(b ? "YES" : "NO"); }public static final void flush() { out.flush(); if(DEBUG) err.flush(); }public static final void assertion(final boolean b) { if(!b) { flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final char c) { if(!b) { errprtln(c); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final boolean b2) { if(!b) { errprtln(b2); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final int x) { if(!b) { errprtln(x); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final long x) { if(!b) { errprtln(x); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final double d) { if(!b) { errprtln(d); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final String s) { if(!b) { errprtln(s); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final Object o) { if(!b) { errprtln(o); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final char... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final boolean... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final int... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final long... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final double... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final String... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final Object[] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final char[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final boolean[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final int[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final long[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final double[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final String[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void assertion(final boolean b, final Object[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }public static final void inclusiveRangeCheck(final int i, final int max) { inclusiveRangeCheck(i, 0, max); }public static final void inclusiveRangeCheck(final int i, final int min, final int max) { rangeCheck(i, min, max + 1); }public static final void inclusiveRangeCheck(final long i, final long max) { inclusiveRangeCheck(i, 0, max); }public static final void inclusiveRangeCheck(final long i, final long min, final long max) { rangeCheck(i, min, max + 1); }public static final void rangeCheck(final int i, final int max) { rangeCheck(i, 0, max); }public static final void rangeCheck(final int i, final int min, final int max) { if(i < min || i >= max) throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, max)); }public static final void rangeCheck(final long i, final long max) { rangeCheck(i, 0, max); }public static final void rangeCheck(final long i, final long min, final long max) { if(i < min || i >= max) throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, max)); }public static final void nonNegativeCheck(final long x) { nonNegativeCheck(x, "the argument"); }public static final void nonNegativeCheck(final long x, final String attribute) { if(x < 0) throw new IllegalArgumentException(String.format("%s%d is negative", attribute, x)); }public static final void positiveCheck(final long x) { positiveCheck(x, "the argument"); }public static final void positiveCheck(final long x, final String attribute) { if(x <= 0) throw new IllegalArgumentException(String.format("%s %dis negative", attribute, x)); }public static final void exit() { flush(); System.exit(0); }public static final void exit(final char c) { prtln(c); exit(); }public static final void exit(final boolean b) { prtln(b); exit(); }public static final void exit(final int x) { prtln(x); exit(); }public static final void exit(final long x) { prtln(x); exit(); }public static final void exit(final double d) { prtln(d); exit(); }public static final void exit(final String s) { prtln(s); exit(); }public static final void exit(final Object o) { prtln(o); exit(); }public static final void exit(final char... a) { prtln(a); exit(); }public static final void exit(final boolean... a) { prtln(a); exit(); }public static final void exit(final int... a) { prtln(a); exit(); }public static final void exit(final long... a) { prtln(a); exit(); }public static final void exit(final double... a) { prtln(a); exit(); }public static final void exit(final String... a) { prtln(a); exit(); }public static final void exit(final Object[] a) { prtln(a); exit(); }public static final void exit(final char[][] a) { prtln(a); exit(); }public static final void exit(final boolean[][] a) { prtln(a); exit(); }public static final void exit(final int[][] a) { prtln(a); exit(); }public static final void exit(final long[][] a) { prtln(a); exit(); }public static final void exit(final double[][] a) { prtln(a); exit(); }public static final void exit(final String[][] a) { prtln(a); exit(); }public static final void exit(final Object[][] a) { prtln(a); exit(); }public static final char booleanToChar(final boolean b) { return b ? '#' : '.'; }public static final char[] booleanToChar(final boolean... a) {final char c[] = new char[a.length];for(int i = 0; i < a.length; i ++) c[i] = booleanToChar(a[i]);return c;}public static final long INF = (long)4e18;public static final boolean isPlusINF(final long x) { return x > INF / 10; }public static final boolean isMinusINF(final long x) { return isPlusINF(- x); }public static final boolean isINF(final long x) { return isPlusINF(x) || isMinusINF(x); }public static final int I_INF = (int)1e9 + 1000;public static final boolean isPlusINF(final int x) { return x > I_INF / 10; }public static final boolean isMinusINF(final int x) { return isPlusINF(- x); }public static final boolean isINF(final int x) { return isPlusINF(x) || isMinusINF(x); }}class Pair extends SimpleUtil {// Pairpublic static final II npii() { return new II(ni(), ni()); }public static final II[] npii(final int n) { final II a[] = new II[n]; for(int i = 0; i < n; i ++) a[i] = npii(); return a; }public static final II[][] npii(final int n, final int m) { final II a[][] = new II[n][m]; for(int i = 0; i < n; i ++) a[i] = npii(m); return a;}public static final IL npil() { return new IL(ni(), nl()); }public static final IL[] npil(final int n) { final IL a[] = new IL[n]; for(int i = 0; i < n; i ++) a[i] = npil(); return a; }public static final LI npli() { return new LI(nl(), ni()); }public static final LI[] npli(final int n) { final LI a[] = new LI[n]; for(int i = 0; i < n; i ++) a[i] = npli(); return a; }public static final LL npll() { return new LL(nl(), nl()); }public static final LL[] npll(final int n) { final LL a[] = new LL[n]; for(int i = 0; i < n; i ++) a[i] = npll(); return a; }public static final class II implements Comparable<II> {public int a; public int b;public II() { }public II(final int a, final int b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;II that = (II) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final II that) { int c = Integer.compare(this.a, that.a); if(c == 0) c = Integer.compare(this.b, that.b); return c; }}public static final class IL implements Comparable<IL> {public int a; public long b;public IL() { }public IL(final int a, final long b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;IL that = (IL) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final IL that) { int c = Integer.compare(this.a, that.a); if(c == 0) c = Long.compare(this.b, that.b);return c; }}public static final class LI implements Comparable<LI> {public long a; public int b;public LI() { }public LI(final long a, final int b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;LI that = (LI) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final LI that) { int c = Long.compare(this.a, that.a); if(c == 0) c = Integer.compare(this.b, that.b);return c; }}public static final class LL implements Comparable<LL> {public long a; public long b;public LL() { }public LL(final long a, final long b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;LL that = (LL) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final LL that) { int c = Long.compare(this.a, that.a); if(c == 0) c = Long.compare(this.b, that.b);return c; }}public static final class ID implements Comparable<ID> {public int a; public double b;public ID() { }public ID(final int a, final double b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;ID that = (ID) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final ID that) { int c = Integer.compare(this.a, that.a); if(c == 0) c = Double.compare(this.b, that.b);return c; }}public static final class LD implements Comparable<LD> {public long a; public double b;public LD() { }public LD(final long a, final double b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;LD that = (LD) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final LD that) { int c = Long.compare(this.a, that.a); if(c == 0) c = Double.compare(this.b, that.b);return c; }}public static final class DI implements Comparable<DI> {public double a; public int b;public DI() { }public DI(final double a, final int b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;DI that = (DI) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final DI that) { int c = Double.compare(this.a, that.a); if(c == 0) c = Integer.compare(this.b, that.b);return c; }}public static final class DL implements Comparable<DL> {public double a; public long b;public DL() { }public DL(final double a, final long b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;DL that = (DL) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final DL that) { int c = Double.compare(this.a, that.a); if(c == 0) c = Long.compare(this.b, that.b);return c; }}public static final class DD implements Comparable<DD> {public double a; public double b;public DD() { }public DD(final double a, final double b) { this.a = a; this.b = b; }@Override public final String toString() { return "("+a+", "+b+")"; }@Override public final int hashCode() { return Objects.hash(a, b); }@Overridepublic boolean equals(final Object obj) {if(this == obj) return true;if(obj == null) return false;if(this.getClass() != obj.getClass()) return false;DD that = (DD) obj;if(this.a != that.a || this.b != that.b) return false;return true;}@Override public final int compareTo(final DD that) { int c = Double.compare(this.a, that.a); if(c == 0) c = Double.compare(this.b, that.b);return c; }}}abstract class Solver extends SimpleUtil implements Runnable {public static void main(final String[] args, Runnable solver) {DEBUG = args.length > 0 && args[0].equals("-DEBUG");Thread.setDefaultUncaughtExceptionHandler((t, e) -> { flush(); e.printStackTrace(); System.exit(1); });new Thread(null, solver, "", 1 << 31).start();}@Overridepublic void run() { solve(); flush(); }abstract public void solve();}public class Main extends Solver {public static void main(final String[] args) { main(args, new Main()); }public void solve() {int n = ni();long a[] = nl(n);Swag swag = new Swag(a, 0, (ele1, ele2) -> gcd(ele1, ele2));long ans = 0;int r = 0;for(int l = 0; l < n; l ++) {for(; r <= n; r ++) {if(swag.fold(l, r) == 1) { ans += n - r + 1; break; }}}prtln(ans);}public static final long gcd(long a, long b) { while(true) { if(b == 0) return a; long tmp = a; a = b; b = tmp % b; } }}class Swag {int n;long val[];long e;LongBinaryOperator f;long front;Deque<Long> back = new ArrayDeque<>();int l = 0;int r = 0;// O(1)Swag(long[] val, long e, LongBinaryOperator f) {n = val.length;this.val = val;this.e = e;this.f = f;front = e;}// O(N + QlogQ)long[] query(Pair.II[] p) {Integer idx[] = new Integer[p.length];Arrays.sort(idx, (ele1, ele2) -> {int c = Integer.compare(p[ele1].a, p[ele2].a);if(c == 0) c = Integer.compare(p[ele1].b, p[ele2].b);if(c == 0) c = Integer.compare(ele1, ele2);return c;});long ans[] = new long[p.length];for(int i : idx) ans[i] = fold(p[i]);return ans;}// O(N + Q)// p is sortedlong[] sortedQuery(Pair.II[] p) {long ans[] = new long[p.length];for(int i = 0; i < p.length; i ++) ans[i] = fold(p[i]);return ans;}// return fold [i, j)long fold(Pair.II p) { return fold(p.a, p.b); }long fold(int i, int j) {SimpleUtil.rangeCheck(i, n);SimpleUtil.inclusiveRangeCheck(j, n);SimpleUtil.assertion(i >= l && j >= r);while(r < j) front = f.applyAsLong(front, val[r ++]);while(l < i) {if(back.isEmpty()) {long tmp = e;for(int u = r - 1; u >= l; u --) {tmp = f.applyAsLong(val[u], tmp);back.addLast(tmp);}front = e;}back.removeLast();l ++;}return back.isEmpty() ? front : f.applyAsLong(back.getLast(), front);}}