Submission #39648686

---

Source Code Expand

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

using ll = long long; 
using ld = long double; 
using str = string; 

using pii = pair<int, int>; 
using pll = pair<ll, ll>; 
#define MP make_pair
#define fs first 
#define sc second

using ull = unsigned long long; 
using mii = map<int, int>; 
using mll = map<ll, ll>; 
#define fd(x, e) (x.find(e) != x.end())

#define tcT template <class T
#define tcTU tcT, class U
#define vt vector //tcT > using vt = vector<T>;
#define ar array // tcT, size_t SZ > using ar = array<T, SZ>;
using vi = vt<int>;
using vb = vt<bool>;
using vl = vt<ll>;
using vd = vt<ld>;
using vs = vt<str>;
using vii = vt<pii>;
using vll = vt<pll>;

#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(x.begin(), x.end()) 
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define ts to_string

#define ub upper_bound
#define lb lower_bound
tcT> int lwb(vt<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
tcT> int upb(vt<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); }

#define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
#define rp2(i, a, e) for (int (i) = (a); (i) < (int) (e); (i)+=1)
#define rp3(i, a, e, s) for (int (i) = (a); (i) < (int) (e); (i)+=(s))
#define	rpr(i, e) for (int (i) = (e) - 1; i > -1; (i)-=1)
#define rp4(i, a, e) for (int (i) = a; (i) > (int) (e); (i)-=1)
#define rp5(i, a, e, s) for (int (i) = a; (i) > (int) (e); (i)+=(s))
#define E(a, x) for (auto &a: x) 

#define nr(a, n) rp(i, n) {cin >> (a)[i];}
#define nr2(a, n, m) rp(i, n)  rp(j, m) cin >> (a)[i][j]; 
#define quick ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const ld PI = acos((ld)-1);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!!
tcT> using pqg = priority_queue<T, vector<T>, greater<T>>;

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr ll pctll(ll x) { return __builtin_popcountll(x); } 
constexpr int bits(
	int x) { // assert(x >= 0); 
	return x == 0 ? 0 : 31 - __builtin_clz(x);
} // floor(log2(x))
// constexpr int p2(int x) { return 1 << x; }
// constexpr int msk2(int x) { return p2(x) - 1; }

// ------ ------ ------ IO ------ ------ ------ //
template <class A> void re(vt<A>& v);
template <class A, size_t S> void re(array<A, S>& a);

tcT> void re(T& x) { 
	cin >> x;
}
void re(double& d) { 
	string t; 
	re(t); 
	d=stod(t); 
}
void re(long double& d) { 
	string t; 
	re(t); 
	d=stold(t); 
}
tcT> void re(pair<T, T> & p) { 
	T a, b; 
	re(a); 
	re(b); 
	p=make_pair(a, b); 
}
template<class H, class... T> void re(H& h, T&... t) {
	re(h); 
	re(t...); 
}
template<class A> void re(vt<A>& x) { 
	for (auto &a: x) re(a); 
}
template<class A, size_t S> void re(array<A, S>& x) { 
	for (auto &a: x) re(a); 
}
string to_string(char c) { 
	return string(1, c); 
}
string to_string(bool b) { 
	return b?"YES":"NO";
}
string to_string(const char* s) { 
	return string(s); }
string to_string(string s) { 
	return s; 
}
string to_string(vt<bool> v) { 
	string res; 
	rp(i, sz(v)) 
		res+=char('0'+v[i]);  
	return res; 
}
template<size_t S> string to_string(bitset<S> b) { 
	string res; 
	rp(i, S)
		res+=char('0'+b[i]);
	return res; 
}
tcT> string to_string(pair<T, T> p) { 
	string res;
	res += to_string(p.first); 
	res += ' '; 
	res += to_string(p.second); 
	return res;
}
tcT> string to_string(vt<T> & v) { 
	bool f=1; 
	string res; 
	for (auto& x: v) { 
		if(!f) 
			res+=' ';
		f=0; 
		res+=to_string(x);
	} 
	return res;
}
template<class A> void write(A x) { 
	cout << to_string(x); 
}
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h); 
	write(t...); 
}
void print() { 
	write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h); 
	if(sizeof...(t)) 
		write(' '); 
	print(t...);
}
void DBG() {
	cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h);
	if(sizeof...(t))
		cerr << ", ";
	DBG(t...);
}
#define wr write
#define ps print
// ------ ------ ------ alg ------ ------ ------ //
tcTU> void sort(vt<T> & a, U f) { 
	sort(a.begin(), a.end(), f); 
}
tcT> void rsor(vt<T> & a) { 
	sort(a.begin(), a.end(), greater<T>()); 
}
void rsor(str & a) { 
	sort(a.begin(), a.end(), greater<char>()); 
}
tcT> void rev(vt<T> & a){ 
	reverse(a.begin(), a.end()); 
}
void rev(str & a){ 
	reverse(a.begin(), a.end()); 
}

#define vmax(x) *max_element(begin(x), end(x))
#define vmin(x) *min_element(begin(x), end(x))
#define umax(x, n) *max_element((x), (x) + (n))
#define umin(x, n) *min_element((x), (x) + (n))

tcT> bool amin(T & a, const T & b) {
	return b<a?a=b, 1:0;
}

tcT> bool amax(T & a, const T & b) {
	return a<b?a=b, 1:0;
}

tcT> T cdiv(T a, T b) {return (a+b-1)/b;} 
 
tcTU> T ftrue(T lo, T hi, U f) { 
	while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } 
	return lo;
}
tcTU> T ltrue(T lo, T hi, U f) {
	while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } 
	return lo;
}

#define ri(...) int __VA_ARGS__; re(__VA_ARGS__);
#define rl(...) ll __VA_ARGS__; re(__VA_ARGS__);
#define rs(...) str __VA_ARGS__; re(__VA_ARGS__);

const int mxn = 2e5 + 10; 
const int inf = 1e9 + 10; 
const int M = 1e9 + 7; 

template <typename T>
T inverse(T a, T m) {
	T u = 0, v = 1;
	while (a != 0) {
		T t = m / a;
		m -= t * a; swap(a, m);
		u -= t * v; swap(u, v);
	}
	assert(m == 1);
	return u;
}

ll md; 

template<class T>
T power(T a, long long b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
    	a %= md; 
        if (b % 2) {
            res *= a;
            res %= md; 
        }
    }
    return res;
}

ll a, x; 

void solve() {
	re(a, x, md); 

	if (a == 1) {
		ps((a * x) % md);  
		return; 
	}
	ll ans = power(a, x); 
	ans = (ans - 1 + md) % md; 
	ans = (ans * ((inverse(a - 1, md) + md) % md)) % md; 
	cout << ans << '\n';
	return;
}

int main() {
	quick; 

	int t = 1; 
	// cin >> t; 
	while (t--) solve(); 

	return 0; 
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

// you should actually read the stuff at the bottom

 

Submission Info

Compile Error

./Main.cpp: In function ‘std::string to_string(std::vector<bool>)’:
./Main.cpp:50:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   50 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:121:2: note: in expansion of macro ‘rp’
  121 |  rp(i, sz(v))
      |  ^~
./Main.cpp: In function ‘std::string to_string(std::bitset<_Nb>)’:
./Main.cpp:50:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   50 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:127:2: note: in expansion of macro ‘rp’
  127 |  rp(i, S)
      |  ^~

Judge Result