type
status
date
slug
summary
tags
category
icon
password
问题
求出的值，其中a，b，c是整数，且，
算法设计
暴力算法
考虑用循环直接求出的值，最后对取模。
这个代码其实有两个缺陷。
- 时间复杂度为，即要进行次运算，一般情况下计算机在1s内无法完成。
- ans会超过long long范围。
下面对其进行优化。我们来看看取模的性质:
所以我们可以在每一次乘的时候都对取模，即
这样我们就解决了缺陷2。但是时间复杂度并没有优化，还有没有别的办法呢？
快速幂算法
我们首先考虑一下手算，，很容易发现规律。而且，这个算法时间复杂度为，时间大大减少。
补充：费马小定理
若为素数，为正整数，且互质。则有。
- Author:Serendipity
- URL:https://serendipity565.netlify.app//article/%E5%BF%AB%E9%80%9F%E5%B9%82
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!