c/c++语言开发共享P2613 【模板】有理数取余 (数论)

题目

p2613 【模板】有理数取余

解析

简单的数论题
发现并没有对小数取余这一说，所以我们把原式化一下，(c=frac{a}{b}equiv atimes b^{-1}(mod p))，因为(p)是质数，所以我们根据费马小定理，有(atimes b^{p-2}equiv c(mod p))，于是我们求(atimes b^{p-2}(mod p))就好了，注意(b=0)时无解。
输入的话根据同余的同加性和同乘性，在读入优化里加一个取余就好了

代码

#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 19260817; int a, b;  inline int read() {     int x = 0, f = 0; char ch = getchar();     while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();     while (isdigit(ch)) x = (x * 10 + ch - '0') % mod, ch = getchar();     return f ? -x : x; }  int qpow(int a, int b) {     int ans = 1;     while (b) {         if (b & 1) ans = (ans * a) % mod;         a = (a * a) % mod, b >>= 1;     }     return ans; }  main() {     a = read(), b = read();     if (b == 0) {         printf("angry!");         return 0;     }     cout << (qpow(b, mod - 2) * a % mod + mod) % mod; }