2019牛客暑期多校训练营（第五场） generator 1 （矩阵快速幂，10进制快速幂 / 指数循环节）

题目链接：https://ac.nowcoder.com/acm/contest/885/B?&headNav=acm

思路：由于给你的指数很大，所以需要用十进制的快速幂（之前都没见过，算是长见识了）耗时1500ms

还有+1大佬独创的求指数循环节的方法  耗时36ms

//这是十进制快速幂
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5; 
struct node {ll a[2][2];
}; 
node mul (node a, node b, ll mod) {node ans;memset(ans.a, 0, sizeof(ans.a));for(int i = 0; i < 2; i++) {for(int j = 0; j < 2; j++) {for(int k = 0; k < 2; k++) {ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;}}}return ans;
} 
char s[maxn]; 
int main()
{ll x, y, a, b, mod;node ans, tmp, aa;scanf("%lld %lld %lld %lld", &x, &y, &a, &b);scanf("%s", s);scanf("%lld", &mod);int t = strlen(s);aa.a[0][0] = a;    aa.a[0][1] = 1;    aa.a[1][0] = b;    aa.a[1][1] = 0;ans.a[0][0] = 1;   ans.a[1][1] = 1;   ans.a[0][1] = 0;   ans.a[1][0] = 0;for(int le = t - 1; le >= 0; le--) {int b = s[le] - '0';tmp.a[0][0] = 1; tmp.a[1][1] = 1;  tmp.a[0][1] = 0; tmp.a[1][0] = 0;for(int i = 0; i < b ; ++i)  ans = mul(ans, aa, mod);for(int i = 0; i < 10 ; ++i)  tmp = mul(tmp, aa, mod);aa = tmp;}   printf("%lld\n", (ans.a[1][1] * x + ans.a[0][1] * y) % mod );return 0;
}

//求指数循环节

//求指数循环节
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
struct node {ll a[2][2];
};int cnt,pri[100000+10];
void init(){ll limit;for(int i = 2; i <= 100000; i++){if(!pri[i]) pri[cnt++] = i;for(int j = 0; j < cnt; j++){limit = 1ll * i * pri[j];if(limit > 100000) break;pri[limit] = 1;if(i%pri[j] == 0) break;}}
}
ll solve(ll x){ll ans1 = 1, ans2=1, xx = x;for(int i = 0; i < cnt; i++){if(1ll * pri[i] * pri[i] > x) break;if(x % pri[i] == 0){ans1 *= (pri[i] - 1) * (pri[i] + 1);ans2 *= pri[i];while(x % pri[i] == 0) x /= pri[i];}}if(x>1){ans1 *= (x - 1) * (x + 1);ans2 *= x;}return xx / ans2 * ans1;
}node mul (node a, node b, ll mod) {node ans;memset(ans.a, 0, sizeof(ans.a));for(int i = 0; i < 2; i++) {for(int j = 0; j < 2; j++) {for(int k = 0; k < 2; k++) {ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;}}}return ans;
}
node ksm(node a, ll b, ll mod) {node ans;ans.a[0][0] = 1;ans.a[1][1] = 1;ans.a[0][1] = 0;ans.a[1][0] = 0;while(b) {if(b & 1) ans = mul(ans, a, mod);a = mul(a, a, mod);b >>= 1;}return ans;
}
char s[maxn];
ll ksc(ll x, ll y, ll z){x %= z;y %= z;ll ans = 0;while(y){if(y & 1){ans += x;if(ans >= z) ans -= z;}x <<= 1;if(x >= z) x -= z;y >>= 1;}return ans;
}
int main()
{ll x, y, a, b, mod, m, n;node ans, aa;scanf("%lld %lld %lld %lld", &x, &y, &a, &b);scanf("%s", s);scanf("%lld", &mod);int t = strlen(s);init();m = solve(mod), n = 0;for(int i = 0; i < t; i++) {n = ksc(n , 10 ,m) ;n = n + s[i] -'0';if(n >= m) n -= m;}aa.a[0][0] = a;aa.a[0][1] = 1;aa.a[1][0] = b;aa.a[1][1] = 0;ans = ksm(aa, n, mod);printf("%lld\n", (ans.a[1][1] * x + ans.a[0][1] * y) % mod );return 0;
}