题解 P2613 【【模板】有理数取余】

不要管高精。。。可以发现，$a$和$b$只有对$mod$的余数才会有用。直接一路滚过去取模即可。至于除法，费马小定理需要了解: $$a^{p-1}\equiv 1\pmod p$$ 推导一下就可以得到: $$a^{p-2}\equiv a^{-1}\pmod p$$ 答案就是 $$a*b^{-1}$$ 直接计算即可。 代码: ```cpp #include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #define For(i,a,b) for(i=(a),i##end=(b);i<=i##end;++i) #define Forward(i,a,b) for(i=(a),i##end=(b);i>=i##end;--i) #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define Chkmax(a,b) a=a>b?a:b #define Chkmin(a,b) a=a<b?a:b using namespace std; template<typename T>inline void read(T &x){ T s=0,f=1;char k=getchar(); while(!isdigit(k)&&k^'-')k=getchar(); if(!isdigit(k)){f=-1;k=getchar();} while(isdigit(k)){s=s*10+(k^48);k=getchar();} x=s*f; } void file(void){ #ifndef ONLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif } const int MAXN=1e4+7; const int mod=19260817; static char a[MAXN],b[MAXN]; static int n,m,A,B; typedef long long ll; inline int power(int a,int b) { static int sum; for(sum=1;b;b>>=1,a=(ll)a*a%mod)if(b&1) sum=(ll)sum*a%mod; return sum; } int main(void){ file(); scanf("%s%s",a,b);n=strlen(a)-1,m=strlen(b)-1; Rep(i,0,n)A=(A*10+(a[i]^48))%mod; Rep(i,0,m)B=(B*10+(b[i]^48))%mod; if(B==0)return puts("Angry!"),0; printf("%d\n",(ll)A*power(B,mod-2)%mod); return 0; } ```