网站建设报价套餐/seo 优化技术难度大吗

本文转自（侵删）：https://blog.csdn.net/GreatJames/article/details/77162961

指数循环节

在有些题目中我们需要对指数进行降幂处理才能计算。比如计算

其中和

这里由于很大，所以需要进行降幂。那么实际上有如下降幂公式

给定，和的值，求的值，其中，

代码： 

#include <iostream>
#include <string.h>
#include <stdio.h>using namespace std;
const int N = 1000005;
typedef long long LL;char str[N];int phi(int n)//求φ(n)
{int rea = n;for (int i = 2; i * i <= n; i++){if (n % i == 0){rea = rea - rea / i;while (n % i == 0){n /= i;}}}if (n > 1){rea = rea - rea / n;}return rea;
}LL multi(LL a, LL b, LL m)//快乘a*b%m
{LL ans = 0;a %= m;while (b){if (b & 1){ans = (ans + a) % m;b--;}b >>= 1;a = (a + a) % m;}return ans;
}LL quick_mod(LL a, LL b, LL m)//快速幂a^b%mod
{LL ans = 1;a %= m;while (b){if (b & 1){ans = multi(ans, a, m);b--;}b >>= 1;a = multi(a, a, m);}return ans;
}void Solve(LL a, char str[], LL c)//a^str%c
{LL len = strlen(str);LL ans = 0;LL p = phi(c);if (len <= 15){for (int i = 0; i < len; i++){ans = ans * 10 + str[i] - '0';}}else{for (int i = 0; i < len; i++){ans = ans * 10 + str[i] - '0';ans %= p;}ans += p;}printf("%I64d\n", quick_mod(a, ans, c));
}int main()
{LL a, c;while (~scanf("%I64d%s%I64d", &a, str, &c)){Solve(a, str, c);}return 0;
}