P2613 【模板】有理数取余 (数论)

题目

P2613 【模板】有理数取余

解析

简单的数论题
发现并没有对小数取余这一说,所以我们把原式化一下,
\[(c=\frac{a}{b})\equiv a\times b^{-1}(mod\ p)\]
因为\(p\)是质数,所以我们根据费马小定理\(b^{p-1}\equiv 1(mod p)\)
\(a\times b^{-1}\times 1 \equiv c(mod\ p)\)
\(=>a\times b^{-1}\times b^{p-1} \equiv c(mod\ p)\)
\(=>a\times b^{p-2} \equiv c(mod\ p)\)
于是我们求\(a\times 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;
}
全部评论

相关推荐

竟然收到了测评听说是双机位
投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务