acm必做50题的解题数论.doc

ACM必做50题的解题-数论
ACM must do 50 problem solving - number theory,.Txt, love is art, marriage is technology, divorce is arithmetic. This year the girls were vying for the small "waist" fine, who rare small "belly" Po? Higher than high salaries, paid as long, long as happy. POJ 1061 frog appointment
This question is used to solve the linear equation of congruence method, have not been exposed before, search data to see a person's blog, which speaks well, copy over. As follows:
The equation: ax = B (MOD m), a, B, m are integers, solving x value, this is the linear congruence equation.
Symbolic description:
MoD said: modulo operation
Ax = B (MOD m) said: (AX - b) mod M = 0, namely congruence
GCD (a b) said: the greatest common divisor of a and B
For Ax = B (MOD n): the principle for the equation AX = B (MOD n), ax + by = GCD (a, b), x, and Y is an integer. Ax = B (MOD n) can be solved by X, making up y. Specific practices are as follows:
The first problem is to solve GCD (a, b)
Theorem 1: GCD (a, b) = GCD (B, a, mod, b)
Euclidean algorithm
Int Euclid (int, a, int, b)
{
If (b = 0)
Return a;
Else
Return Euclid (B, mod (a, b));
}
Attachment: modulo operation
Int mod (int, a, int, b)
{
If (a = 0)
Return a% b;
Else
Return a% B + b;
}
The second problem: solving ax + by = GCD (a, b)
Theorem two: ax +, by = GCD (a, b) = GCD (B, a, mod, b) = b * X'+ (a, mod, b) * Y'
= b * X'+ (a - A / b * b) * Y'
= a * Y'+ b * (X' - A / b * Y')
= a * x + b * y
Then: x = Y'
Y = X'- A / b * Y'
The above content is transferred from /redcastle/blog/item/
Extended Euclidean algorithms can be derived from this:
Int, exGcd (int, a, int, B, int, &x, int, &y)
{
If (b = 0)
{
X = 1;
Y = 0;
Return a;
}
Int, r = exGcd (B, a,%, B, x, y);
Int t = x;
X = y;
Y = t - A / b * y;
Return r;
}
Code：
#include<iostream>
#in