結果
| 問題 | No.1871 divisXor |
| ユーザー |
 shojin_pro
|
| 提出日時 | 2022-03-11 22:48:47 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,626 bytes |
| コンパイル時間 | 2,627 ms |
| コンパイル使用メモリ | 82,220 KB |
| 実行使用メモリ | 112,568 KB |
| 最終ジャッジ日時 | 2023-10-14 08:04:28 |
| 合計ジャッジ時間 | 19,312 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 295 ms
109,068 KB |
| testcase_01 | AC | 41 ms
49,592 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | AC | 292 ms
108,596 KB |
| testcase_23 | AC | 292 ms
109,212 KB |
| testcase_24 | AC | 296 ms
108,808 KB |
| testcase_25 | AC | 294 ms
108,568 KB |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
ソースコード
import java.util.*;
import java.io.*;
public class Main {
static ContestScanner sc = new ContestScanner(System.in);
static PrintWriter pw = new PrintWriter(System.out);
static StringBuilder sb = new StringBuilder();
static long mod = (long)998244353;
public static void main(String[] args) throws Exception {
solve();
pw.flush();
}
public static void solve() {
long N = sc.nextLong();
if(N == 0){
pw.println(-1);
return;
}
ArrayList<Long> arr = new ArrayList<>();
HashSet<Long> set = new HashSet<>();
long total = 0;
long max = 2L*N;
Sieve s = new Sieve(10000000);
while(N != 0 && arr.size() <= 100 && total < max){
if(set.contains(N)){
pw.println(-1);
return;
}
if(N == 1){
arr.add(1L);
break;
}
if(N < 10000000 && s.isPrime((int)N-1) && !set.contains(N-1)){
arr.add(N-1);
break;
}
long sqrt = (long)Math.sqrt(N);
long tmp = 1+N;
long minV = N;
for(int i = 2; i <= sqrt; i++){
if(N % i == 0){
if(!set.contains(N/i)) minV = Math.min(minV,i);
tmp += N/i;
if(N/i != i)tmp += i;
}
}
if(minV == N){
arr.add(N);
set.add(N);
N ^= tmp;
total += N;
}else{
long tmp2 = N/minV;
sqrt = (long)Math.sqrt(tmp2);
tmp = 1+tmp2;
for(int i = 2; i <= sqrt; i++){
if(N % i == 0){
tmp += tmp2/i;
if(N/i != i)tmp += i;
}
}
arr.add(tmp2);
set.add(tmp2);
N ^= tmp;
total += tmp2;
}
}
if(arr.size() > 100 || total >= max){
pw.println(-1);
return;
}
pw.println(arr.size());
for(long v : arr){
sb.append(v).append(" ");
}
pw.println(sb.toString());
}
static class GeekInteger {
public static void save_sort(int[] array) {
shuffle(array);
Arrays.sort(array);
}
public static int[] shuffle(int[] array) {
int n = array.length;
Random random = new Random();
for (int i = 0, j; i < n; i++) {
j = i + random.nextInt(n - i);
int randomElement = array[j];
array[j] = array[i];
array[i] = randomElement;
}
return array;
}
public static void save_sort(long[] array) {
shuffle(array);
Arrays.sort(array);
}
public static long[] shuffle(long[] array) {
int n = array.length;
Random random = new Random();
for (int i = 0, j; i < n; i++) {
j = i + random.nextInt(n - i);
long randomElement = array[j];
array[j] = array[i];
array[i] = randomElement;
}
return array;
}
}
}
class Sieve{
static int n;
static int[] f;
static ArrayList<Integer> prime;
public Sieve(int n){
long ln = n;
prime = new ArrayList<Integer>();
f = new int[n+1];
f[0] = f[1] = -1;
for(int i = 2; i <= n; i++){
if(f[i] != 0){
continue;
}
f[i] = i;
prime.add(i);
long li = (long)i;
for(long j = li*li; j <= ln; j += li){
if(f[(int)j] == 0){
f[(int)j] = i;
}
}
}
}
public static boolean isPrime(int x){
return f[x] == x;
}
public static ArrayList<Integer> factorList(int x){
ArrayList<Integer> res = new ArrayList<Integer>();
while(x != 1){
res.add(f[x]);
x /= f[x];
}
return res;
}
public static HashMap<Integer,Integer> factor(int x){
ArrayList<Integer> fl = factorList(x);
HashMap<Integer,Integer> res = new HashMap<Integer,Integer>();
if(fl.size()==0){
return new HashMap<Integer,Integer>();
}
int prev = fl.get(0);
int cnt = 0;
for(int p : fl){
if(prev == p){
cnt++;
}else{
res.put(prev,cnt);
prev = p;
cnt = 1;
}
}
res.put(prev,cnt);
return res;
}
}
/**
* refercence : https://github.com/NASU41/AtCoderLibraryForJava/blob/master/ContestIO/ContestScanner.java
*/
class ContestScanner {
private final java.io.InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private static final long LONG_MAX_TENTHS = 922337203685477580L;
private static final int LONG_MAX_LAST_DIGIT = 7;
private static final int LONG_MIN_LAST_DIGIT = 8;
public ContestScanner(java.io.InputStream in){
this.in = in;
}
public ContestScanner(java.io.File file) throws java.io.FileNotFoundException {
this(new java.io.BufferedInputStream(new java.io.FileInputStream(file)));
}
public ContestScanner(){
this(System.in);
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
buflen = in.read(buffer);
} catch (java.io.IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++]; else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
public boolean hasNext() {
while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new java.util.NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new java.util.NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
int digit = b - '0';
if (n >= LONG_MAX_TENTHS) {
if (n == LONG_MAX_TENTHS) {
if (minus) {
if (digit <= LONG_MIN_LAST_DIGIT) {
n = -n * 10 - digit;
b = readByte();
if (!isPrintableChar(b)) {
return n;
} else if (b < '0' || '9' < b) {
throw new NumberFormatException(
String.format("%d%s... is not number", n, Character.toString(b))
);
}
}
} else {
if (digit <= LONG_MAX_LAST_DIGIT) {
n = n * 10 + digit;
b = readByte();
if (!isPrintableChar(b)) {
return n;
} else if (b < '0' || '9' < b) {
throw new NumberFormatException(
String.format("%d%s... is not number", n, Character.toString(b))
);
}
}
}
}
throw new ArithmeticException(
String.format("%s%d%d... overflows long.", minus ? "-" : "", n, digit)
);
}
n = n * 10 + digit;
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public long[] nextLongArray(int length){
long[] array = new long[length];
for(int i=0; i<length; i++) array[i] = this.nextLong();
return array;
}
public long[] nextLongArray(int length, java.util.function.LongUnaryOperator map){
long[] array = new long[length];
for(int i=0; i<length; i++) array[i] = map.applyAsLong(this.nextLong());
return array;
}
public int[] nextIntArray(int length){
int[] array = new int[length];
for(int i=0; i<length; i++) array[i] = this.nextInt();
return array;
}
public int[] nextIntArray(int length, java.util.function.IntUnaryOperator map){
int[] array = new int[length];
for(int i=0; i<length; i++) array[i] = map.applyAsInt(this.nextInt());
return array;
}
public double[] nextDoubleArray(int length){
double[] array = new double[length];
for(int i=0; i<length; i++) array[i] = this.nextDouble();
return array;
}
public double[] nextDoubleArray(int length, java.util.function.DoubleUnaryOperator map){
double[] array = new double[length];
for(int i=0; i<length; i++) array[i] = map.applyAsDouble(this.nextDouble());
return array;
}
public long[][] nextLongMatrix(int height, int width){
long[][] mat = new long[height][width];
for(int h=0; h<height; h++) for(int w=0; w<width; w++){
mat[h][w] = this.nextLong();
}
return mat;
}
public int[][] nextIntMatrix(int height, int width){
int[][] mat = new int[height][width];
for(int h=0; h<height; h++) for(int w=0; w<width; w++){
mat[h][w] = this.nextInt();
}
return mat;
}
public double[][] nextDoubleMatrix(int height, int width){
double[][] mat = new double[height][width];
for(int h=0; h<height; h++) for(int w=0; w<width; w++){
mat[h][w] = this.nextDouble();
}
return mat;
}
public char[][] nextCharMatrix(int height, int width){
char[][] mat = new char[height][width];
for(int h=0; h<height; h++){
String s = this.next();
for(int w=0; w<width; w++){
mat[h][w] = s.charAt(w);
}
}
return mat;
}
}