Cryptopangrams

给一种加密方法, 就是找到从[2,N]之间的prime, 然后sort, 然后分别给他们26个字母表示, 然后两两交叉相成后, 得到加密后的文字. 现在给一个加密文字, 求decoding后的明文. 这个题主要是找到如何decode, 首先观察输入数据的大小, 10^100, 这个等级double 肯定不行, 所以要用BigInteger. 其次, 因为是两两相乘, 所以中间肯定共享一位, 所以要用到gcd, 这里正好java的biginteger有自带gcd方法, 只要找到不相等的两项做了gcd, 那么出来的结果肯定是A*(gcd)*C这个模式, 就知道前边和后边的项了. 所以只用做一次gcd. 最后, 只需要找到连续不相同的两项做gcd, 然后用while往左和右分别扫一次即可.

import java.math.BigInteger;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        for (int i = 1; i <= n; i++) {
            String[] strs = scanner.nextLine().split(" ");
            String[] ecs = scanner.nextLine().split(" ");
            BigInteger[] nums = new BigInteger[ecs.length];
            for (int k = 0; k < ecs.length; k++) {
                nums[k] = new BigInteger(ecs[k]);
            }
            String res = solve(new BigInteger(strs[0]), Integer.valueOf(strs[1]), nums);
            System.out.println("Case #" + i + ": " + res);
        }
    }


    private static String solve(BigInteger N, int L, BigInteger[] nums) {
        StringBuilder sb = new StringBuilder();
        SortedSet<BigInteger> set = new TreeSet<>();
        List<BigInteger> decoded = new ArrayList<>();
        int i = 0;
        while(i + 1 < nums.length && nums[i].equals(nums[i+1])) {
            i++;
        }
        BigInteger gcd = nums[i].gcd(nums[i+1]);
        decoded.add(nums[i].divide(gcd));
        decoded.add(gcd);
        decoded.add(nums[i+1].divide(gcd));
        BigInteger tmp = nums[i].divide(gcd);
        int t = i;
        t--;
        while (t>=0) {
            decoded.add(0,nums[t].divide(tmp));
            tmp = nums[t].divide(tmp);
            t--;
        }
        tmp = nums[i+1].divide(gcd);
        int s = i;
        s+=2;
        while (s < nums.length) {
            decoded.add(nums[s].divide(tmp));
            tmp = nums[s].divide(tmp);
            s++;
        }
        set.addAll(decoded);
        Map<BigInteger, Character> integerCharacterMap = new HashMap<>();
        Iterator<BigInteger> integerIterator = set.iterator();
        int tt = 0;
        while (integerIterator.hasNext()) {
            integerCharacterMap.put(integerIterator.next(), (char) ('A' + tt++));
        }
        for (BigInteger n : decoded) {
            sb.append(integerCharacterMap.get(n));
        }
        return sb.toString();
    }
}