結果

問題 No.2637 Factorize?
コンテスト
ユーザー sysnote8main
提出日時 2024-04-12 17:21:53
言語 Java
(openjdk 23)
結果
AC  
実行時間 153 ms / 2,000 ms
コード長 5,057 bytes
コンパイル時間 2,636 ms
コンパイル使用メモリ 93,892 KB
実行使用メモリ 41,820 KB
最終ジャッジ日時 2024-10-02 22:49:46
合計ジャッジ時間 8,108 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
    private static final SynIO logger = new SynIO();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        List<Long> l = MathLib.divisors(n);
        logger.clog(l.get(0), n/l.get(0));
//        if(SynLib.isPrime(n)) {
//            logger.clog(n, 1);
//        } else {
//            long f = MathLib.gcd(n);
//            logger.clog(f, (long) n/f);
//        }
    }
}

// === LIBRARY AREA ===

// sysnote8's Library
class SynIO {
    private final String prefix;
    public SynIO() {
        this("");
    }
    public SynIO(String prefix) {
        this.prefix = prefix;
    }

    public void log(String s) {
        System.out.println(prefix + s);
    }

    public void log(Object... objects) {
        for(Object o: objects) {
            log(o.toString());
        }
    }

    public void clog(Object... objects) {
        StringJoiner sj = new StringJoiner(" ");
        for(Object obj: objects) {
            sj.add(obj.toString());
        }
        log(sj.toString());
    }
}

class SynLib {
    public static boolean isPrime(long n) {
        if(n%2==0) return false;
        for(long i = 3; i < n; i+=2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static boolean isPrimeAdv(long n) {
        return MathLib.gcd(n) == 1;
    }
}



// Atcoder Library For Java
// https://github.com/NASU41/AtCoderLibraryForJava

// From https://github.com/NASU41/AtCoderLibraryForJava/blob/master/Math/MathLib.java
class MathLib {
    private static long safe_mod(long x, long m){
        x %= m;
        if(x<0) x += m;
        return x;
    }

    private static long[] inv_gcd(long a, long b){
        a = safe_mod(a, b);
        if(a==0) return new long[]{b,0};

        long s=b, t=a;
        long m0=0, m1=1;
        while(t>0){
            long u = s/t;
            s -= t*u;
            m0 -= m1*u;
            long tmp = s; s = t; t = tmp;
            tmp = m0; m0 = m1; m1 = tmp;
        }
        if(m0<0) m0 += b/s;
        return new long[]{s,m0};
    }

    public static long gcd(long... a){
        if(a.length == 0) return 0;
        long r = java.lang.Math.abs(a[0]);
        for(int i=1; i<a.length; i++){
            if(a[i]!=0) {
                if(r==0) r = java.lang.Math.abs(a[i]);
                else r = inv_gcd(r, java.lang.Math.abs(a[i]))[0];
            }
        }
        return r;
    }

    public static long lcm(long... a){
        if(a.length == 0) return 0;
        long r = java.lang.Math.abs(a[0]);
        for(int i=1; i<a.length; i++){
            r = r / gcd(r,java.lang.Math.abs(a[i])) * java.lang.Math.abs(a[i]);
        }
        return r;
    }

    public static long pow_mod(long x, long n, int m){
        assert n >= 0;
        assert m >= 1;
        if(m == 1)return 0L;
        x = safe_mod(x, m);
        long ans = 1L;
        while(n > 0){
            if((n&1) == 1) ans = (ans * x) % m;
            x = (x*x) % m;
            n >>>= 1;
        }
        return ans;
    }

    public static long[] crt(long[] r, long[] m){
        assert(r.length == m.length);
        int n = r.length;

        long r0=0, m0=1;
        for(int i=0; i<n; i++){
            assert(1 <= m[i]);
            long r1 = safe_mod(r[i], m[i]), m1 = m[i];
            if(m0 < m1){
                long tmp = r0; r0 = r1; r1 = tmp;
                tmp = m0; m0 = m1; m1 = tmp;
            }
            if(m0%m1 == 0){
                if(r0%m1 != r1) return new long[]{0,0};
                continue;
            }

            long[] ig = inv_gcd(m0, m1);
            long g = ig[0], im = ig[1];

            long u1 = m1/g;
            if((r1-r0)%g != 0) return new long[]{0,0};

            long x = (r1-r0) / g % u1 * im % u1;

            r0 += x * m0;
            m0 *= u1;
            if(r0<0) r0 += m0;
            //System.err.printf("%d %d\n", r0, m0);
        }
        return new long[]{r0, m0};
    }
    public static long floor_sum(long n, long m, long a, long b){
        long ans = 0;
        if(a >= m){
            ans += (n-1) * n * (a/m) / 2;
            a %= m;
        }
        if(b >= m){
            ans += n * (b/m);
            b %= m;
        }

        long y_max = (a*n+b) / m;
        long x_max = y_max * m - b;
        if(y_max == 0) return ans;
        ans += (n - (x_max+a-1)/a) * y_max;
        ans += floor_sum(y_max, a, m, (a-x_max%a)%a);
        return ans;
    }

    public static java.util.ArrayList<Long> divisors(long n){
        java.util.ArrayList<Long> divisors = new ArrayList<>();
        java.util.ArrayList<Long> large = new ArrayList<>();

        for(long i=1; i*i<=n; i++) if(n%i==0){
            divisors.add(i);
            if(i*i<n) large.add(n/i);
        }
        for(int p=large.size()-1; p>=0; p--){
            divisors.add(large.get(p));
        }
        return divisors;
    }
}
0