习惯写法
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define forr(i,a) for(auto i:a)
#define all(a) begin(a), end(a)
ABC293-E
倍增 O(logX)
等比数列求和为 AX−1A−1, 可能A−1与M不互质,没有逆元
考虑递推, 矩阵
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e5 + 10;
LL a, x, m;
void mul(LL c[2][2], LL a[2][2], LL b[2][2])
{
static LL t[2][2];
memset(t, 0, sizeof t);
for(int i = 0; i < 2; i ++)
for(int j = 0; j < 2; j ++)
for(int k = 0; k < 2; k ++)
t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % m;
memcpy(c, t, sizeof t);
}
int main()
{
scanf("%lld%lld%lld", &a, &x, &m);
LL f[2][2] = {
{a, 1},
{0, 1}
};
LL A[2][2] = {
{1, 0},
{0, 1}
};
while(x)
{
if(x & 1) mul(A, A, f);
mul(f, f, f);
x >>= 1;
}
printf("%lld", A[0][1]);
return 0;
}
也可以对等比数列公式进行变形
AX−1A−1=Mq+r=>AX−1=Mq(A−1)+r(A−1)=>(AX−1)%M(A−1)=r(A−1)=>r=(AX−1)%((A−1)M)A−1
#include<bits/stdc++.h>
using namespace std;
typedef __int128 LL;
LL a, x, m;
LL qmi(LL a, LL b, LL p)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int main()
{
scanf("%lld%lld%lld", &a, &x, &m);
if(a == 1) printf("%lld", x % m);
else
printf("%lld", ((qmi(a, x, m * (a - 1)) - 1) % (m * ( a - 1)) + (m * ( a - 1))) % (m * ( a - 1)) / (a - 1));
return 0;
}