Submission #16886573

---

Source Code Expand

// Problem : E - Sequence Sum
// Contest : AtCoder - AtCoder Beginner Contest 179
// URL : https://atcoder.jp/contests/abc179/tasks/abc179_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)


/*ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀🌙｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、 
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 🚶ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/

// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,b,a) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define bug(x) cout<<#x<<"="<<x<<endl; 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001; //check the limits, dummy
 
int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);    
	ll N;
	int X,M;
	cin>>N>>X>>M;
	ll val=X,sum=0;
	vi m(M+1);
	vl sm(M+1);
	FOR(x,1,N+1)
	{
		m[val]=x;
		sum+=val;
		sm[x]=sum;
		val=(val*val)%M;
		ll cpy=val;
		if(val==0)
		{
			cout<<sum<<nl;
			return 0;
		}
		if(val==1)
		{
			cout<<sum+N-x;
			return 0;
		}
		if(m[val])
		{
			N-=x;//?
			ll quo=N/(x-m[val]+1);//?
			N%=x-m[val]+1;
			sum+=(sm[x]-sm[m[val]-1])*quo;//?
			break;
		}
	}
	while(N-->0)//?
	{
		sum+=val;
		val=(val*val)%M;
	}
	cout<<sum;
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79:6: warning: unused variable ‘cpy’ [-Wunused-variable]
   79 |   ll cpy=val;
      |      ^~~

Judge Result