同余方程可变换
x≡a/b (%p)
==> x*b≡a (%p)
==> bx+p*y=a
==> x=x0+p/gcd(b,p)
#include<bits/stdc++.h>
using namespace std;
namespace{
template<typename T>
inline void read(T &s){
T f=1;s=0;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f=-1;
for(;isdigit(ch);ch=getchar()) s=((s<<1)+(s<<3)+(ch^48))%19260817;
}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
int exgcd(int a,int b,ll& x,ll& y){ //
if(b==0){
x=1;y=0;
return a;
}
int res=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return res;
}
ll a,b,x,y;
int main(){
read(a);read(b);
//cout << a << b;
int p=19260817;
ll g_cd=exgcd(b,p,x,y);
if(a%g_cd){
cout << "Angry!\n";return 0;
}
x=(x%p+p)%p;
(x*=a)%=p;
cout << x;
return 0;
}

京公网安备 11010502036488号