竞赛讨论区 > H题 why wa
头像
苏梦枕
编辑于 2020-01-20 18:13
+ 关注

H题 why wa

下面这段代码为啥会错?能给组数据么?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    static int n;
    static int k;
    static int N = 500;
    static int[][] map = new int[N + 1][N + 1];
    static int PNum = 95;
    static int[] prime = new int[PNum];

    public static void main(String[] args) throws NumberFormatException, IOException {
        pre();
        init();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String[] words = br.readLine().split("\\s+");
            n = Integer.parseInt(words[0]);
            k = Integer.parseInt(words[1]);

            boolean flag = false;
            long min = Long.MAX_VALUE;
            for (int i = 2; i <= k ; i++) {
                if (k % i == 0) {
                    for (int x = i; x <= n; x += i) {
                        int count = 0;
                        for (int y = 1; y <= n; y++) {
                            if (map[x][y] == i) {
                                count++;
                            }
                        }
                        if (count == 1 ) {
//                            System.out.println(x);
                            if( x < min) {
                                min = x;
                            }
                            flag = true;
//                            break;
                        }
                    }

                }
            }
            if (!flag) {
                BigInteger res = BigInteger.ONE;
                for (int i = 0; i < PNum; i++) {
                    if (prime[i] <= n) {
                        res = res.multiply(BigInteger.valueOf((long) prime[i]));
                    }
                }
                
                if ( res.compareTo(BigInteger.valueOf( Long.MAX_VALUE)) > 0 ){
                    System.out.println(-1);
                }
                else {
                    System.out.println(res);
                }
            }else {
                System.out.println(min);
            }

        }
    }

    private static int gcd(int i, int j) {
        if (j % i == 0) {
            return i;
        } else {
            return gcd(j % i, i);
        }
    }

    private static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int g = gcd(i, j);
                map[j][i] = g;
            }
        }
    }
    

    private static void pre() {
        int count = 0;
        for (int i = 2; i <= N; i++) {
            int j = (int) Math.sqrt((double) i);
            boolean flag = false;
            for (int t = 2; t <= j; t++) {
                if (i % t == 0) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
    //            System.out.print(i + " ");
                prime[count] = i;
                count++;
            }
        }
//        System.out.println("\n" + count);
    }

}



全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐