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;

}

巴特西

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

题目

解析

代码

最新文章

热门文章