poj1006

數論跪了三天。。

這個題不難得到(n+d)%23=p;   (n+d)%28=e;   (n+d)%33=i

如何求解？

首先介紹一個所謂“逆”的概念。

給定整數a，有（a，m）=1，稱ax=1(mod m)的一個解叫做a模m的逆。

下面給出求逆的程序。

#include <iostream>   
#include <math.h>   
  
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) <<endl;  
    }  
}