您现在的位置: 主页 > 华夏黑客联盟 > 盗QQ密码 > 文章内容

PKU2891黑客破解相册

作者: QQ黑客 来源:未知 时间: 2013-12-13 阅读:
黑客源码大全java]
package D0718;
 
/*
 * 题目大体意思就是求x%ai=ri要求x的最小值
 * 中国剩余定理
 * 对于同余方程组:
 * x=a1 (mod m1)
 * x=a2 (mod m2)
 * 方程组有一个小于m(m1,m2的最小公倍数)的非负整数解的充要条件是(a1-a2)%gcd(m1,m2)=0,同样利用扩展欧几里得算法。两式联立:a1+m1*y=a2+m2*z
 * 则:a1-a2=m2*z-m1*y这样就可以解出z和y,则:x=a2+m2*z
 * 而对于一般情形:(设m1,m2,...mk两两互素)时有:
 * a=b[1] (mod w[1])
 * a=b[2] (mod w[2])
 * .....
 * a=b[n] (mod w[n])
 * 其中w,b已知,w[1],w[2]...w[n]是两两互素的正整数,求a
 * 令W=w[1]*w[2]*...w[n],用W[i]=W/w[i],因为gcd(W[i],w[i])=1,故有;两整数p[i],q[i]满足W[i]*p[i]+w[i]*q[i]=1;如果记e[i]=W[i]*p[i],那么当j!=i时有:e[i]=0 (mod w[j]),当j=i时有:e[i]=1 (mod w[j]);
 * 所以很明显:e[1]*b[1]+e2*b[2]+......e[k]*b[k]就是方程的一个解,加减W倍后就可以得到最小非负整数解了
 * 而对于w[1],w[2].....w[n]不互素的情形,就只能两个两个来求了
 * x=a[1] (mod m[1])
 * x=a[2] (mod m[2])
 * 解完后,a=x,m=m1和m2的最小公倍数
 * 将题目意思转化为公式:a1*x-a2*y=r2-r1,用欧几里得扩展算法求解
 * */
import java.util.Scanner;
 
public class PKU2891 {
    static boolean flag;
    static long d, x, y;
    static long result;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a1, m1, m2, a2, k;
        while (sc.hasNext()) {
            k = sc.nextLong();
            m1 = sc.nextLong();
            a1 = sc.nextLong();
            k -= 1;
            flag = false;
            result = 0;
            x = y = 0;
            d = 0;
            for (int i = 0; i < k; i++) {
                m2 = sc.nextLong();
                a2 = sc.nextLong();
                long b = a2 - a1;
                d = extend_GCD(m1, m2);
                if (b % d != 0)
                    flag = true;// 不存在整数解
                result = (x * (b / d) % m2 + m2) % m2;
                a1 = a1 + m1 * result; // 对于求多个方程
                m1 = (m1 * m2) / d; // lcm(m1,m2)最小公倍数;d是m1 和 m2 的最大公约数
                a1 = (a1 % m1 + m1) % m1;
            }
            if (flag)
                System.out.println(-1);
            else
                System.out.println(a1);
        }
 
    }
 
    // 扩展的欧几里德
    private static long extend_GCD(long a, long b) {
        long ret, t;
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        ret = extend_GCD(b, a % b);
        t = x;
        x = y;
        y = t - (a / b) * y;
        return ret;
    }
}
作者:黑客盗Q技巧

本篇文章来源于 黑客基地-专业的QQ黑客技术最优秀密码破解网站!