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

\(c\)等于一个分数，求他的余数，分数是不能直接模的，除以一个数等于乘上这个数的逆元。

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

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

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

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

貌似博客里写的东西还出锅了，又被\(lfd\)一顿嘲笑。\(233\)（卑微.jpg

他讲的数论我当时确实是听得很明白啊，可是后来又忘了......

#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【模板】有理数取余

最新文章

热门文章