同余方程：
1)如果两个整数a,b，那么必定存在公式a*x+b*y=gcd(a,b);
2)方程 ax + by = m 有解的必要条件是 m mod gcd(a,b) = 0

同余：设m是给定的一个正整数，a、b是整数，若满足 m|(a-b)，则称a与b对模m同余，记为a≡b(mod m)，或记为a≡b(m)
意义相当于 a=b+km(k∈Z)；
扩展欧几里得算法可以用来计算模反元素(也叫模逆元)

一）碾转相除法求gcd
　　int gcd(int m,int n){   return m%n==0?n:gcd(n,m%n);}
　　int gcd(int m,int n){   return n==0 ? m:gcd(n,m%n);}//或

二）扩展欧几里德，可以同时求出最小的x,y;
模板：
 int gcdEx(int a,int b,int*x,int*y)
{
    if(b==0)
    {
        *x=1,*y=0 ;
        return a ;
    }
    else
    {
        int r=gcdEx(b,a%b,x,y);
       
        int t=*x ;
        *x=*y ;
        *y=t-a/b**y ;
        return r ;
    }
}

一）同余方程 P1082 扩展欧几里德模板
求关于x的同余方程 ax≡1(mod b) 的最小正整数解。
输入格式
一行，包含两个正整数 a,b，用一个空格隔开。
输出格式
一个正整数 x_0，即最小正整数解。输入数据保证一定有解。
输入输出样例
输入 #1复制
3 10
输出 #1复制
7
说明/提示
【数据范围】
对于 40%的数据，2≤b≤1,000；
对于 60%的数据，2≤b≤50,000,000；
对于 100%的数据，2≤a,b≤2,000,000,000。
NOIP 2012 提高组 第二天 第一题

可以用暴力枚举x，拿40-60分，但是要AC，需要使用扩展欧几里德
条件 ax mod b = 1，实质是 ax + by = 1，y是任意整数，因为by mod b一定等于0;
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b){
    if(b==0)  {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b);
    k=x, x=y, y=k-a/b*y;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>a>>b;
    exgcd(a,b);
    cout<<(x+b)%b;
}

二）A/B hdu1576　逆元模板
要求(A/B) mod 9973，但由于A很大，我们只给出n(n=A mod 9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B) mod 9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060

逆元的定义：
每个数a均有唯一的与之对应的乘法逆元x，使得a*x≡1(mod M)，一个数有逆元的充分必要条件是gcd(a,M)=1，此时a的逆元x唯一存在。
在这题里，M==9973，与B存在gcd(B,M)==1的关系。因此B相对于9973的逆元是x.
A/B mod 9973的意义，等价于A*x mod 9973。
而(A+n) mod 9973 =n，即 A=n (mod 9973)，所以答案是n*x
逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

解法一：扩展欧几里德，也就是求逆元
给定模数9973，求B的逆元，相当于求解Bx=1(mod 9973) ,
即存在B*x+9973*y=1的关系；y可以是任何数；
两侧取mod 9973，就得到
B*x mod 9973 =1


#include "bits/stdc++.h"
using namespace std;
const int md=9973;
typedef long long ll;
ll ex_gcd(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll r = ex_gcd(b,a%b,y,x);
    y -= x*(a/b);
    return r;
}//扩展欧几里得模板
int main(){
    ll n,B,t,gcd,x,y;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&B);
        gcd = ex_gcd(B,md,x,y);
        x =(x*n)%md; //x=A/B,贝祖定理, n =A mod 9973
        x = (x+md) % md;
        printf("%lld\n",x);
    }
    return 0;
}

解法二：相当于解释了贝祖定理的形成。
本題由题意n=A mod 9973,
改写成n=A-A/9973*9973
因为A/B=X;所以A=n+A/9973*9973=BX;
得到 BX-9973y=n；
因为gcd(B,9973)==1，所以B*X＋9973*y==1存在x,y的整数解，
因此b*x-n一定存在正整数解，并且等于9973*n
由x*B-n=9973y，得到(x*B-n)mod 9973=0，类似《我家的门牌号》

using namespace std;  
int main()  
{  
    int t, i, j;  
    long long n, b, a=9973;  
    scanf("%d", &t);  
    while(t--)
    {  
        scanf("%lld%lld", &n, &b);  
        for(x=0; x < a; j++)  
            if((x * b - n) % a == 0) {  //b*x -n==9973*y;
                printf("%d\n", x);  
                break;  
            }  
    }  
    return 0;  
}

三）RSA　hdu1211
RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:
> choose two large prime integer p, q
> calculate n = p × q, calculate F(n) = (p - 1) × (q - 1)
> choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key
> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key
You can encrypt data with this method :
C = E(m) = me mod n
When you want to decrypt data, use this method :
M = D(c) = cd mod n
Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.
Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.
Input
Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks.
Output
For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.
Sample Input
101 103 7 11
7716 7746 7497 126 8486 4708 7746 623 7298 7357 3239
Sample Output
I-LOVE-ACM.
Source
杭电ACM省赛集训队选拔赛之热身赛

RSA是个很强大的加密数据的工具，对RSA系统的描述如下：
选择两个大素数p、q，计算n = p * q，F(n) = (p-1)*(q-1)，选择一个整数e，使得gcd(e，F(n)) = 1，
e是公匙，计算d使得d * e mod F(n) = 1 mod F(n)，d是私匙。加密数据的方法为
C = E(m) = m^e mod n
解密数据的方法为
M = D(c) = c^d mod n
其中，c是密文中字母的ASCII的值；m是明文中字母的ASCII的值。
给你p、q、e和一些密文，请把密文翻译成明文。

#include "bits/stdc++.h"
#define ll long long
using namespace std;
void ex_gcd(ll a, ll b, ll &d, ll &x, ll & y) {
     if(!b){ d = a; x = 1; y = 0; }
     else{ ex_gcd(b, a%b, d, y, x); y -= x*(a/b); }
}
ll MultiPower(ll a,ll b,ll mo)
{
    int res = 1;
    while(b > 0)
    {
        if(b&1)
            res = res * a % mo;
        a = a*a % mo;
        b >>= 1;
    }
    return res;
}
int main()
{
    ll p,q,e,l,d;
    while(cin >> p >> q >> e >> l)
    {
        ll n = p*q;
        p = (p-1)*(q-1);
        ll x0,y0;
        ex_gcd(e,p,d,x0,y0);
        x0 = (x0%p + p) % p;
        for(ll i = 0; i < l; ++i)
        {
            cin >> d;
            ll m = MultiPower(d,x0,n);
            printf("%c",m8);
        }
        printf("\n");
    }
    return 0;
}

五）谈恋爱　hdu2669
The Sky is Sprite.
The Birds is Fly in the Sky.
The Wind is Wonderful.
Blew Throw the Trees
Trees are Shaking, Leaves are Falling.
Lovers Walk passing, and so are You.

Girls are clever and bright. In HDU every girl like math. Every girl like to solve math problem!
Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.
Input
The input contains multiple test cases.
Each case two nonnegative integer a,b (0 < a, b<=2^31)
Output
output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put "sorry" instead.
Sample Input
77 51
10 44
34 79
Sample Output
2 -3
sorry
7 -3
题目大意：给两个数a和b，找出一组x，y使得a*x + b*y = 1，如果找不出输出sorry
题解：显然是用扩展欧几里得定理求解。
扩展欧几里德算法
基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
#define ll long long
using namespace std;
ll x,y;
void ex_gcd(ll a, ll b, ll &d, ll &x, ll & y) {
     if(!b){ d = a; x = 1; y = 0; }
     else{ ex_gcd(b, a%b, d, y, x); y -= x*(a/b); }
}
ll cal(ll a,ll m,ll c){
    ll gcd;
    ex_gcd(a,m,gcd,x,y);
    if( (c%gcd)!=0 ) return -1;
    x*=c/gcd;
    m/=gcd;
    ll ans = xs(m);
    if(ans<=0) ans+=m;
    return ans;
}
 
int main(){
    ll a,b;
    while(~scanf("%lld%lld",&a,&b)){
        ll temp = cal(a,b,1);
        if(temp == -1) printf("sorry\n");
        else printf("%lld %lld\n",temp,(1-temp*a)/b);        
    }
    return 0;
}