小数第N位【快速幂（快速指数）算法】--数论

小数第N位--数论 题目【快速幂取模】代码快速幂模板代码

题目

【快速幂取模】代码 //小数第n位 #include <iostream> #include <vector> #include <string> #include <algorithm> #include <math.h> #include <queue> #include <cctype> using namespace std; //快速幂算法：pow_mod //实现(base^exponent) % mod long long pow_mod(long long base, long long exponent, long long mod) { long long result = 1; base %= mod; while (exponent > 0) { if (exponent % 2 == 1) { result = (result * base) % mod; } base = (base * base) % mod; exponent /= 2; } return result; } int main() { int a, b, n; cin >> a >> b >> n; int mod = b * 1000; //计算 n 位开始的 3 位数字，固结果的范围是 [0, 999]，固b*1000按3位数进行分组 int res = a * pow_mod(10, n + 2, mod) % mod / b; //若指数较小可换成：int res = int(int(a * pow(10, n + 2)) % mod) / b; //(a × 10^(n+2)) % (b × 1000) //实现a/b的小数点前是第n+3位 对 b×1000 取模，保留最后3位 //为避免溢出固使用用【快速幂算法】-log(n) //pow()复杂度为n printf("%03d", res); //实现位数不够补足0 return 0; } 快速幂模板代码 #include <iostream> using namespace std; long long pow_mod(long long base, long long n ) { long long r = 1; while (n > 0) { if (n % 2 == 1) r = r * base; base *= base; n /= 2; } return r; } int main() { cout << pow_mod(2, 10); return 0; }