题目
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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603263.html