【模板】有理数取余

嘟嘟嘟

 

a / b % p = a * b^-1 % p，又因为p是质数，根据费马小定理=> a * b^-1 % p = a * b^p-2 % p。

看数据范围，不想写高精，就改了一下快读。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int mod = 19260817;
inline ll read()
{
    ll ans = 0;
    char ch = getchar(), last = ' ';
    while(!isdigit(ch)) {last = ch; ch = getchar();}
    while(isdigit(ch)) {ans = ans * 10 % mod + ch - '0'; ch = getchar();}
    ans %= mod;
    if(last == '-') ans = -ans;
    return ans;
}
inline void write(ll x)
{
    if(x < 0) x = -x, putchar('-');
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}

ll quickpow(ll a, int b)
{
    ll ret = 1;
    while(b)
    {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return ret;
}

int main()
{
    ll a = read(), b = read();
    if(!b) {printf("Angry!\n"); return 0;}
    ll ans = a * quickpow(b, mod - 2) % mod;
    write(ans); enter;
}