首页 > 专题系列 > Java解POJ > POJ 2109 Power of Cryptography [解题报告] Java
2013
11-10

POJ 2109 Power of Cryptography [解题报告] Java

Power of Cryptography

问题描述 :

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers among these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be only of theoretical interest.

This problem involves the efficient computation of integer roots of numbers.

Given an integer n>=1 and an integer p>= 1 you have to write a program that determines the n th positive root of p. In this problem, given such integers n and p, p will always be of the form k to the nth. power, for an integer k (this integer is what your program must find).

输入:

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<=n<= 200, 1<=p<10101 and there exists an integer k, 1<=k<=109 such that kn = p.

输出:

For each integer pair n and p the value k should be printed, i.e., the number k such that k n =p.

样例输入:

2 16
3 27
7 4357186184021382204544

样例输出:

4
3
1234

解题代码:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
 
    static final BigInteger TWO = new BigInteger("2");
    static final BigInteger ONE = BigInteger.ONE;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // k^n=p findK;
          BigInteger p;
          int n;
        BigInteger ks, kl;
        while (in.hasNextInt()) {
            boolean find=false;
            n = in.nextInt();
            p = in.nextBigInteger();
            ks = ONE;
            kl = p;
            while (ks.compareTo(kl) <= 0) {
                BigInteger mid = ks.add(kl).divide(TWO);
                int ret = mid.pow(n).compareTo(p);
                if (ret == 0) {
                    find=true;
                    System.out.println(mid);
                    break;
                } else if (ret == -1) {
                    ks = mid.add(ONE);
                } else {
                    kl = mid.subtract(ONE);
                }
            }
            if(!find){
                System.out.println(ks.subtract(ONE));
            }
        }

    }
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  4. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。