poj1006

数论跪了三天。。

这个题不难得到(n+d)%23=p; (n+d)%28=e; (n+d)%33=i

如何求解？

首先介绍一个所谓“逆”的概念。

给定整数a，有（a，m）=1，称ax=1(mod m)的一个解叫做a模m的逆。

下面给出求逆的程序。

#include    
#include    
  
using namespace std;  
  
typedef long long LL;  
  
void gcd(LL a, LL b, LL &d, LL &x, LL &y)  
{  
    if(!b)  
    {  
        d = a, x = 1, y = 0;  
    }  
    else  
    {  
        gcd(b, a %b, d, y, x);  
        y -= x * (a/b);  
    }  
}  
LL inv(LL a, LL n)  
{  
    LL d, x, y;  
    gcd(a,n,d,x,y);  
    return d == 1   (x + n) % n : -1;  
}  
int main()  
{  
    LL a, m;  
    while(cin>> a>>m)  
    {  
        cout << inv(a, m) <