Cryptopangrams
给一种加密方法, 就是找到从[2,N]之间的prime, 然后sort, 然后分别给他们26个字母表示, 然后两两交叉相成后, 得到加密后的文字. 现在给一个加密文字, 求decoding后的明文. 这个题主要是找到如何decode, 首先观察输入数据的大小, 10^100, 这个等级double 肯定不行, 所以要用BigInteger. 其次, 因为是两两相乘, 所以中间肯定共享一位, 所以要用到gcd, 这里正好java的biginteger有自带gcd方法, 只要找到不相等的两项做了gcd, 那么出来的结果肯定是A*(gcd)*C这个模式, 就知道前边和后边的项了. 所以只用做一次gcd. 最后, 只需要找到连续不相同的两项做gcd, 然后用while往左和右分别扫一次即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
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(); } } |