Thực hiện phép toán
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Suggester:
Problem type
Allowed languages
C++, PyPy, Python
Cho 3 số nguyên A, X, M. hãy tìm ~T=\sum_{k=0}^{X-1}A^{k} module M~.
Đầu vào:
dòng chứa 3 số nguyên A X M trong đó (1 ≤ A,M ≤ ~10^9~; 1≤ X ≤ ~10^{16}~)
Đầu ra:
In ra kết quả phép toán T
Ví dụ:
Input
3 4 7
Output
5
Input
8 10 9
Output
0
Input
1000000000 1000000000000 998244353
Output
919667211
In case the statement didn't load correctly, you can download the statement here: Statement
Comments
include<bits/stdc++.h>
using namespace std; long long mu(long long a,long long b,long long m) { if (b==0) return 1; long long T=mu(a,b/2,m)%m; if (b%2==1) return(((TT)%m)(a%m))%m; else return(T*T)%m;
} main(){ long long a, x, m, T=0; cin>>a>>x>>m; if(a==1) cout<<x%m; else{ long long N = a-1; T=(Nm + mu(a,x,Nm)-1)%(m*N); cout<<T/N;
}