Language: C

#include <bits/stdc++.h>
#define liml 1000010
#define ll long long
const int g = 2;
const ll p = 200003;
ll ans;
int w1[liml],w2[liml],w3[liml];
int a[liml],n;

namespace FFT {
	int mod;
	namespace Math {
		inline int pw(int base, int p, const int mod) {
			static int res;
			for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
			return res;
		}
		inline int inv(int x, const int mod) { return pw(x, mod - 2, mod); }
	}
	
	const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
	const long long mod_1_2 = static_cast<long long> (mod1) * mod2;
	const int inv_1 = Math::inv(mod1, mod2), inv_2 = Math::inv(mod_1_2 % mod3, mod3);
	struct Int {
		int A, B, C;
		explicit inline Int() { }
		explicit inline Int(int __num) : A(__num), B(__num), C(__num) { }
		explicit inline Int(int __A, int __B, int __C) : A(__A), B(__B), C(__C) { }
		static inline Int reduce(const Int &x) {
			return Int(x.A + (x.A >> 31 & mod1), x.B + (x.B >> 31 & mod2), x.C + (x.C >> 31 & mod3));
		}
		inline friend Int operator + (const Int &lhs, const Int &rhs) {
			return reduce(Int(lhs.A + rhs.A - mod1, lhs.B + rhs.B - mod2, lhs.C + rhs.C - mod3));
		}
		inline friend Int operator - (const Int &lhs, const Int &rhs) {
			return reduce(Int(lhs.A - rhs.A, lhs.B - rhs.B, lhs.C - rhs.C));
		}
		inline friend Int operator * (const Int &lhs, const Int &rhs) {
			return Int(static_cast<long long> (lhs.A) * rhs.A % mod1, static_cast<long long> (lhs.B) * rhs.B % mod2, static_cast<long long> (lhs.C) * rhs.C % mod3);
		}
		inline int get() {
			long long x = static_cast<long long> (B - A + mod2) % mod2 * inv_1 % mod2 * mod1 + A;
			return (static_cast<long long> (C - x % mod3 + mod3) % mod3 * inv_2 % mod3 * (mod_1_2 % mod) % mod + x) % mod;
		}
	} ;
	
	#define maxn 262144
	
	namespace Poly {
	#define N (maxn << 1)
		int lim, s, rev[N];
		Int Wn[N | 1];
		inline void init(int n) {
			s = -1, lim = 1; while (lim < n) lim <<= 1, ++s;
			for (register int i = 1; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
			const Int t(Math::pw(G, (mod1 - 1) / lim, mod1), Math::pw(G, (mod2 - 1) / lim, mod2), Math::pw(G, (mod3 - 1) / lim, mod3));
			*Wn = Int(1); for (register Int *i = Wn; i != Wn + lim; ++i) *(i + 1) = *i * t;
		}
		inline void NTT(Int *A, const int op = 1) {
			for (register int i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
			for (register int mid = 1; mid < lim; mid <<= 1) {
				const int t = lim / mid >> 1;
				for (register int i = 0; i < lim; i += mid << 1) {
					for (register int j = 0; j < mid; ++j) {
						const Int W = op ? Wn[t * j] : Wn[lim - t * j];
						const Int X = A[i + j], Y = A[i + j + mid] * W;
						A[i + j] = X + Y, A[i + j + mid] = X - Y;
					}
				}
			}
			if (!op) {
				const Int ilim(Math::inv(lim, mod1), Math::inv(lim, mod2), Math::inv(lim, mod3));
				for (register Int *i = A; i != A + lim; ++i) *i = (*i) * ilim;
			}
		}
	#undef N
	}
	
	int n, m;
	Int A[maxn << 1], B[maxn << 1];
	int conv(int *a,int *b,int n,int m,int *c) {
		mod = p-1;
		++n, ++m;
		for (int i = 0, x; i < n; ++i) A[i] = Int(a[i] % mod);
		for (int i = 0, x; i < m; ++i)  B[i] = Int(b[i] % mod);
		Poly::init(n + m);
		Poly::NTT(A), Poly::NTT(B);
		for (int i = 0; i < Poly::lim; ++i) A[i] = A[i] * B[i];
		Poly::NTT(A, 0);
		for (int i = 0; i < n + m - 1; ++i) 
			c[i] = A[i].get();
		return 0;
	}
}

ll qpow(ll a,ll b){
	if (b==0)return 1;
	ll d=qpow(a,b>>1);d=d*d%p;
	if (b&1)d=d*a%p;
	return d;
}

ll BSGS(ll x){
	std::map<ll,ll>vis;
	ll B=std::sqrt(p)+1;
	ll g1 = qpow(g,B);
	for(ll b=0,w=1;b<=B;++b){
		vis[x*w%p]=b;
		w=w*g%p;
	}
	for(ll a=1,w=g1;a<=B;++a){
		if (vis.count(w)){
			ll d=a*B-vis[w];
			return d==0?p-1:d;
		}w = w*g1 % p;
	}
	assert(0);
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if (!a[i]) continue;
		int d = BSGS(a[i]);
		w1[d]++; w2[d]++;
	} 
	FFT::conv(w1,w2,p,p,w3);
	for (int i=1;i<p;++i) w3[i+i] = (w3[i+i] - w1[i] + (p-1)) % (p-1);
	for(int i=1;i<2*p;++i)  {
		ans += qpow(g,i) * w3[i] / 2;
	//	if (w3[i]) printf("%d %d\n",i,w3[i]);
	}
	printf("%lld",ans);
	return 0;
}
	



Compiler output:
main.c:1:10: fatal error: bits/stdc++.h: No such file or directory
    1 | #include <bits/stdc++.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.