首页 > 专题系列 > Java解POJ > POJ 3892 RSA Factorization [解题报告] Java
2013
11-13

POJ 3892 RSA Factorization [解题报告] Java

RSA Factorization

问题描述 :

The positive integer n is given. It is known that n = p * q, where p and q are primes, q <= p and |q – kp| <= 105 for some given positive integer k. You must find p and q.

输入:

Each line contains integers n (1 < n < 10120) and k (0 < k < 108).

输出:

For each pair of numbers n and k print in separate line the product p * q such that q <= p.

样例输入:

35 1 
121 1 
1000730021 9

样例输出:

5 * 7 
11 * 11 
10007 * 100003

解题代码:

//* @author: 
/*题目说 q <= p and |q - kp| <= 10^5这个条件很重要,说明了p,q的距离很近在10^5之内

其实就是等价于k*p-q<=10^5 ---> k*p*q-q*q<=10^5*q,然后又有n=q*p ---->n*k=q*p*k

所以就是q^2>=n*k-10^5*q,所以就可以确定q和p是在sqrt(n*k)附近,于是向sqrt(n*k)两边暴力枚举...
*/
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
 public static BigInteger sqrt(BigInteger a)
 {
  BigInteger l=BigInteger.ONE,r=a,mid;
  while(r.subtract(l).compareTo(BigInteger.ONE)>0)
  {
   mid = (l.add(r)).divide(BigInteger.valueOf(2));
   if((mid.multiply(mid)).compareTo(a)>0)
    r=mid;
   else if((mid.multiply(mid)).compareTo(a)==0)
    return mid;
   else
    l=mid;
  }
  return l;
 }
 public static void main(String[] args)
 {
  Scanner cin = new Scanner ( System.in );
  BigInteger n,p,k=BigInteger.ONE;
  while(cin.hasNext())
  {
   n = cin.nextBigInteger();
   p = cin.nextBigInteger();
   k = sqrt(n.multiply(p));
   //   System.out.println(k);
   BigInteger a,b;
   a=b=k;
   while(true)
   {
    if(n.mod(a).equals(BigInteger.ZERO) && !a.equals(n)&& !a.equals(BigInteger.ONE))
    {
     b = n.divide(a);
     break;
    }
    if(n.mod(b).equals(BigInteger.ZERO) && !b.equals(n)&& !b.equals(BigInteger.ONE))
    {
     a = n.divide(b);
     break;
    }
    a=a.subtract(BigInteger.ONE);
    b=b.add(BigInteger.ONE);
   }
   if(a.compareTo(b)>0)
   {
    k=a;
    a=b;
    b=k;
   }
   System.out.println(a+" * "+b);
  }

 }
}

  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。