洛谷p2613【模板】有理数取余

题目

因为题目里说了这是一道模板题，所以他是模板题，\(c\)等于一个分数，求他的余数，分数是不能直接模的，除以一个数等于乘上这个数的逆元。

所以此题就是求一个逆元，费马小定理求逆元是很方便的，一个快速幂就解决了。

还要注意因为\(a,b\)的值都很大，在读入的时候需要取模

但是这样只能拿到\(90\)分，最后一个点过不了，什么原因？我们还没有判断这个\(b\)是否有逆元，判断这个数是否有逆元的方法，也不难，只需判断\(gcd(b, mod)\)是否为\(1\)即可。

话说我自己写过博客的我都忘了，做题的时候回来看的\(233\)

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 19260817;
long long a, b, ans;
long long read() {
    long long s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) s = s * 10 + ch - '0', s %= N, ch = getchar();
    return s * w;
}
long long power(long long x, long long y) {
    long long sum = 1;
    while(y) {
        if(y & 1) sum = (sum * x) % N;
        x = (x * x) % N;
        y >>= 1; 
    }
    return sum;
}
long long gcd(long long x, long long y) {
    return y == 0 ? x : gcd(y, x % y);
}
int main() {
    a = read(), b = read();
    if(gcd(b, N) != 1) printf("Angry!\n");
    else cout << (a * power(b, N - 2)) % N << endl;
    return 0;
}

谢谢收看，祝身体健康！

洛谷p2613【模板】有理数取余

原文：https://www.cnblogs.com/yanxiujie/p/11790235.html