Problem:


Score : 800 points

Problem Statement

Let’s take a prime P = 200\,003.
You are given N integers A_1, A_2, \ldots, A_N.
Find the sum of ((A_i \cdot A_j) \bmod P) over all N \cdot (N-1) / 2 unordered pairs of elements (i < j).

Please note that the sum isn't computed modulo P.

Constraints

2 \leq N \leq 200\,000

0 \leq A_i < P = 200\,003

All values in input are integers.

Input

Input is given from Standard Input in the following format.

N
A_1 A_2 \cdots A_N

Output

Print one integer — the sum over ((A_i \cdot A_j) \bmod P).

Sample Input 1

4
2019 0 2020 200002

Sample Output 1

474287

The non-zero products are:

2019 \cdot 2020 \bmod P = 78320

2019 \cdot 200002 \bmod P = 197984

2020 \cdot 200002 \bmod P = 197983

So the answer is 0 + 78320 + 197984 + 0 + 0 + 197983 = 474287. 

Sample Input 2

5
1 1 2 2 100000

Sample Output 2

600013



Sample input:
4
2019 0 2020 200002


Sample output:
474287

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def main2():
    n = int(std_in())
    a = list(get_ints())
    ans = 0
    mod = 200003

    for i in range(n-1):
        for j in range(i+1, n):
            ans += a[i] * a[j] % mod
    print(ans)


def main():
    n = int(std_in())
    a = list(get_ints())
    a = [ai for ai in a if ai != 0]
    a.sort()
    a_1 = a[:-1]
    ans = 0
    mod = 200003

    for i, ai in enumerate(a_1):
        tmp = 0
        for j in range(1, a[-1]+1):
            target = a[i+1:]
            tmp += ai
            if j in target:
                ans += (tmp * target.count(j)) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
j = 0
s = 0
for i in range (N - 1):
    i = 0
    j = j + 1
    for i in range (j):
        if not A[i] == 0 and not A[j] == 0:  
            s = s + (A[i] * A[j]) % 200003
        i = i + 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def maina():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	p=200003
	cc=[0]*p
	for v in al:
		cc[v]+=1
		
	ret = 0
	for i in range(p):
		ret += ((i*i)%p)*(cc[i]*(cc[i]-1)//2)
		for j in range(i+1,p):
			ret += ((i*j)%p)*cc[i]*cc[j]
	print(ret)
	
def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	p=200003
	ret = 0
	for i, vi in enumerate(al):
		for vj in al[i+1:]:
			ret += (vi*vj)%p
			
			
	print(ret)
			
			
			
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def main2():
    n = int(std_in())
    a = list(get_ints())
    ans = 0
    mod = 200003

    for i in range(n-1):
        for j in range(i+1, n):
            ans += a[i] * a[j] % mod
    print(ans)


def main():
    n = int(std_in())
    a = list(get_ints())
    a = [ai for ai in a if ai != 0]
    a.sort()
    a_1 = a[:-1]
    ans = 0
    mod = 200003

    for i, ai in enumerate(a_1):
        tmp = 0
        for j in range(1, a[-1]+1):
            target = a[i+1:]
            tmp += ai
            tmp %= mod
            if j in target:
                ans += (tmp * target.count(j)) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def inverse(a, mod):
    a %= mod
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod

n = int(input())
a = list(map(int, input().split()))
a.sort()
mod = 200003

imos = [0] * (mod + 1)
s = 0
for x in a:
    s = (s + x)
    imos[x] += 1

for i in range(len(imos)-1, 0, -1):
    imos[i - 1] += imos[i]

ans = 0
for x in a:
    if x == 0:
        continue
    ans += x * (s - x)
    for i in range(1, mod + 1):
        y0 = math.ceil(mod * i / x)
        y1 = math.ceil(mod * (i + 1) / x)
        ans -= i * mod * (imos[y0] - imos[min(mod, y1)])
        if y0 <= x < y1:
            ans += i * mod
        if y1 > 200000:
            break
print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int,read().split())

MOD = 200003
#b0 = BIT(MOD)
#b1 = BIT(MOD)

#a = list(range(1000))

bucket = [0]*MOD
b0 = [0]*MOD
b1 = [0]*MOD

for i in a:
    bucket[i] += 1
    b0[i] += 1
    b1[i] += i

from itertools import accumulate
b0 = list(accumulate(b0)) + [0]
b1 = list(accumulate(b1)) + [0]

#print(b1[-5:])
#print(b0[-5:])

ans = 0
for x in range(1,MOD):
    if bucket[x]==0: continue
    b = bucket[x]

    ans -= b*(x*x%MOD)
    #print(x,b)
    #ans -= b*b*(x*x%MOD)
    l = r = 0
    for k in range(1,MOD+10):
        if r>=MOD-1: break
        r = (MOD*k-1)//x
        if r >= MOD: r = MOD-1
        
        c = l*x%MOD
        #if b0[r] - b0[l]: print(l,r,x,c+l*x,"q",(b0[r] - b0[l]),(b1[r] - b1[l]),"d",b*((c-l*x)*(b0[r] - b0[l]) + x*(b1[r] - b1[l]))  )
        #ans += b*(c-l*x)*b0.query(l,r)
        #ans += b*x*b1.query(l,r)
         
        ans += b*((c-l*x)*(b0[r] - b0[l-1]) + x*(b1[r] - b1[l-1]))

        l = r+1

    #print(ans)

#print(ans)
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:

n,ais = int(raw_input()), map(int, raw_input().split())
cumul = 0 
p = 200003
ais.sort()
for i in range(len(ais)):
	q = 0
	prev = 0
	if ais[i]:
		for j in range(i+1, len(ais)):
			if ais[j] - prev > 0:
				q += ais[i] * (ais[j] - prev)
				q %= p
				prev = ais[j]
			cumul += q 
print cumul

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list = [i for i in a_list if i != 0]
total = 0
for i in range(len(a_list)):
    for j in range(i+1, len(a_list)):
        total += (a_list[i] * a_list[j]) % 200003

print(total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()))
MOD = 200003
#MOD = 13
C = [0] * (MOD + 1)
for a in A:
  C[a] = 1
for i in range(1, MOD):
  C[i] += C[i-1]
C[MOD] = C[MOD-1]
#print(C)

t = 0  # sum aiaj//MOD
for a in A:
  current = 0
  for i in range(a):
    tmp = C[(i+1) * MOD // a]
    t += (tmp - current) * (i)
    #print(a, i, (i+1) * MOD // a, (tmp - current) * (i))
    current = tmp
  #print(a, t)
  t -= a * a // MOD

t *= MOD
S = sum(A)
S2 = S * S
for a in A:
  S2 -= a*a
#print(S2, t)
ans = S2 - t
ans //= 2
print(ans)

#ans2=0
#for a in A:
#  for b in A:
#    if a > b:
#      ans2 += a * b % MOD
#print(ans2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
p = 200003
for i in range(n):
    for j in range(i + 1, n):
        ans += (a[i] * a[j]) % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n,ais = int(raw_input()), map(int, raw_input().split())
cumul = 0 
p = 200003
for i in range(len(ais)):
	if ais[i]:
		for j in range(i+1, len(ais)):
			cumul += ais[i] * ais[j] % p
print cumul

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
sum = 0
P =200003
d = 0


for i in range(N):
	for j in range(i+1,N):
		sum +=a[i]*a[j]%P

	

print(sum)


#9872..8332

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
C = Counter(A)

mod = 200003

table = [0]*mod
for a, v in C.items():
    if not a:
        continue
    for i in range(1, mod):
        j = -((-i*mod)//a)
        if j >= mod:
            break
        table[j] += v

for i in range(1, mod):
    table[i] += table[i-1]

geta = 0
for a, v in C.items():
    geta += v*table[a]

sa = sum(A)**2
tt = sa - geta*mod
#print(tt)
for a in A:
    tt -= a*a%mod

print(tt//2)

"""
cnt = 0
for a in A:
    for b in A:
        cnt += a*b%mod

print(cnt)
"""

Submission status: Time Limit Exceeded

Solution code:
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int,read().split())

MOD = 200003
b0 = BIT(MOD)
b1 = BIT(MOD)

bucket = [0]*MOD
for i in a:
    bucket[i] += 1

ans = 0
for x in range(1,MOD):
    if bucket[x]==0: continue

    b = bucket[x]
    #print(x,b)
    #ans -= b*b*(x*x%MOD)
    l = r = 0
    for k in range(1,MOD+10):
        if r==MOD-1: break
        r = (MOD*k-1)//x
        if r >= MOD: r = MOD-1
        
        c = l*x%MOD
        #print(l,r,x,c+l*x,"q",b0.query(l,r),b1.query(l,r),"d",b*(c+l*x)*b0.query(l,r)-b*x*b1.query(l,r))
        #ans += b*(c-l*x)*b0.query(l,r)
        #ans += b*x*b1.query(l,r)
        ans += b*((c-l*x)*b0.query(l,r) + x*b1.query(l,r))

        l = r+1

    #print(ans)
    ans += b*(b-1)//2 * (x*x%MOD)
    b0.add(x,b)
    b1.add(x,b*x)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
P=200003
N=int(input())
*A,=map(int,input().split())

A=[a for a in A if a!=0]
N=len(A)

S=0
for i in range(N-1):
  for j in range(i+1,N):
     S+= A[i]*A[j] %P

print(S)

Submission status: Time Limit Exceeded

Solution code:
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int,read().split())

MOD = 200003
b0 = BIT(MOD)
b1 = BIT(MOD)

bucket = [0]*MOD
for i in a:
    bucket[i] += 1

ans = 0
for x in range(1,MOD):
    if bucket[x]==0: continue

    b = bucket[x]
    #print(x,b)
    #ans -= b*b*(x*x%MOD)
    l = r = 0
    for k in range(1,MOD+10):
        if r==MOD-1: break
        r = (MOD*k-1)//x
        if r >= MOD: r = MOD-1
        
        c = l*x%MOD
        #print(l,r,x,c+l*x,"q",b0.query(l,r),b1.query(l,r),"d",b*(c+l*x)*b0.query(l,r)-b*x*b1.query(l,r))
        ans += b*(c-l*x)*b0.query(l,r)
        ans += b*x*b1.query(l,r)

        l = r+1

    #print(ans)
    ans += b*(b-1)//2 * (x*x%MOD)
    b0.add(x,b)
    b1.add(x,b*x)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lst=list(map(int,input().strip().split()))
mod=200003
s=0 
for k in range(0,n):
    for j in range(k+1,n):
        s+=((lst[k]%mod*lst[j]%mod)%mod)
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0

B = [i for i in A if i != 0]

for i in range(len(B)):
    for j in range(i):
        ans += (B[i]*B[j])%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
for i in input().split():
	if i == "0":
		pass
	else:
		a.append(int(i)%200003)

cnt = 0
for i in range(len(a)):
	for j in range(i+1,len(a)):
			cnt += (a[i]*a[j])%200003


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
  
P=200003
l=list(map(int,input().split()))
sum=0
for i in range(n-1):
    for j in range(i+1,n):
        sum=sum+(l[i]*l[j])%P
print(sum)

Submission status: Time Limit Exceeded

Solution code:
# your code goes here
p=200003
n = int(input())
l = list(map(int,input().split()))
s=0
for i in range(n):
	for j in range(i+1,n):
		s+=((l[i]%p)*(l[j]%p))%p
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
data = list(map(int, input().split(' ')))
p = 200003
lst=[]
for d in data:
    lst.append(d%p)
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        cnt += lst[i]*lst[j]%p
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# Coding is about expressing your feeling and there is always a better way to express your feeling _feelme
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(arr, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if arr[mid] == val:return mid
        elif arr[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,arr):
    for i in range(1,n):arr[i]+=arr[i-1]
    return arr;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
# @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ code here @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
mod=200003
from functools import lru_cache
@lru_cache(None)
def fun(a,b,mod):
    return (a*b)%mod
n = ii1()
arr = iia()
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=fun(arr[i],arr[j],mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0

for i in range(N):
    for j in range(i):
        if A[i] == 0:
            break
        ans += (A[i]*A[j])%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = 0
data = list(map(lambda x: int(x) if int(x) < 100001 else int(x) - 200003, input().split(" ")))
for i in range(N-1):
    a = data[i]
    for j in range(i+1, N):
        b = data[j]
        S += a*b % 200003
print(S)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
aa = [i for i in a if a!=0]
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        ans += (a[i]*a[j])%200003
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
while 0 in A:
    A.remove(0)
P = 200003
sum = 0
for i in range(len(A)):
    for j in range(i+1,len(A)):
        sum += A[i]*A[j]%P
print(sum)

Submission status: Time Limit Exceeded

Solution code:
P = 200003
N = int(input())
s = list(map(int,input().split(" ")))

if 0 in s:
    s.remove(0)
ans = 0
while len(s) != 0:
    ans += sum(list(map(lambda x: (x * s[0])%P ,s[1:])))
    s.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
r = 0
for i in range(n):
    for j in range(i + 1, n):
        r += (a[i] * a[j]) % 200003
print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num_list = input().split()
  
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    if num_list[i] == "0" or num_list[j] == "0":
      continue
    ans += (int(num_list[i])*int(num_list[j])) % 200003
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
P = 200003
ans = 0
for i in range(N):
  A[i] = A[i] % P
for i in range(N):
  if A[i] == 0:
    continue
  for j in range(i+1, N):
    if A[j] == 0:
      continue
    ans = ans + ((A[i] * A[j]) % P)
print (ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(lambda x: int(x), input().split()))
modulo = 0

for i, a_i in enumerate(a):
    for j, a_j in enumerate(a[i+1:]):
        modulo += a_i * a_j % 200003
print(modulo)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = 200003
ans = 0
for i in range(n):
    for j in range(1,n - i):
        ans += a[i]*a[i + j] % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
num_list = input().split()
  
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    ans += (int(num_list[i])*int(num_list[j])) % 200003
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
P = 200003
sum = 0
for i in range(N):
    if A[i] == 0:
        continue
    for j in range(i+1,N):
        if A[j] == 0:
            continue
        sum += A[i]*A[j]%P
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = 200003
b = []
for i in range(n):
    for j in range(1,n - i):
        b.append(a[i]*a[i + j] % p)
print(sum(b))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0

for i in range(N):
    for j in range(i):
        ans += (A[i]*A[j])%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
arr = list(map(int, input().split()))
s = 0
P = 200003

for pair in itertools.combinations(arr, r=2):
    s += ((pair[0]*pair[1])%P)

print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0

Bn = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(i):
        ans += (A[i]*A[j])%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
P = 200003
N = int(input())
s = list(map(int,input().split(" ")))

ans = 0
while len(s) != 0:
    tmp = s[0]
    s.pop(0)
    ans += (sum(list(map(lambda x: (x * tmp)%P ,s))))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int, input().split()))
t=0
for i in range(0,n-1):
    for j in range(i+1,n):
        if a[i]<=100000 or a[j]<=100000:
            t = t + (a[i]*a[j])%200003
        else:
            t = t + ((a[i]-200003)*(a[j]-200003))%200003
print(t)

Submission status: Time Limit Exceeded

Solution code:
n = int(input()) 
  
# Below line read inputs from user using map() function  
lst = list(map(int,input().strip().split()))[:n] 


count=0
for i in range(0,len(lst)-1):
    for j in range(i+1,len(lst)):
        count+=(lst[i]*lst[j])%200003

print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def main():
    n = int(std_in())
    a = list(get_ints())
    ans = 0
    mod = 200003

    for i in range(n-1):
        for j in range(i+1, n):
            ans += a[i] * a[j] % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def mul(x, y, mod):
    x %= mod
    y %= mod
    return x * y % mod


def main():
    n = int(std_in())
    a = list(get_ints())
    ans = 0
    mod = 200003

    for i in range(n-1):
        for j in range(i+1, n):
            ans += mul(a[i], a[j], mod)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
i = 0
j = 1
s = 0
for i in range (N - 1):
    for i in range (j):
        if not A[i] == 0 and not A[j] == 0:  
            s = s + (A[i] * A[j]) % 200003
        i = i + 1
    i = 0
    j = j + 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ls1 = [int(i) for i in input().split()]
sum = 0
for i in range(n):
    for j in range(i+1,n):
        sum += (ls1[i] * ls1[j])%200003
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
i = 0
j = 1
s = list()
for i in range (N - 1):
    for i in range (j):
        if not A[i] == 0 and not A[j] == 0: 
            o = A[i] * A[j]
            s.append (o % 200003)
        i = i + 1
    i = 0
    j = j + 1
print(sum(s))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
P = 200003
sum = 0
for i in range(N):
    if A[i] == 0:
        continue
    for j in range(i+1,N):
        sum += A[i]*A[j]%P
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
i = 0
j = 1
s = list()
for i in range (N - 1):
    for i in range (j):
        o = A[i] * A[j]
        s.append (o % 200003)
        i = i + 1
    i = 0
    j = j + 1
print(sum(s))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0

An = np.array([A for _ in range(N)])

AnAn = An * An.T

P = AnAn%mod

for i in range(N):
    for j in range(i):
        ans += P[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
P=200003
N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N):
  if A[i]==0:
    continue
  for j in range(i+1,N):
    ans+=(A[i]*A[j])%P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int, input().split()))
j = 0
for p in range(0,n):
    for q in range(p+1,n):
         j = j + (s[p]*s[q])%200003
print(j)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int, input().split()))

t=0
for i in range(0,n-1):
    for j in range(i+1,n):
        t = t + (a[i]*a[j])%200003

print(t)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
nums=list(map(int, input().split(" ")))

result_sum=[]
k=1
for i in range(N):
  for j in range(k, N):
    a = nums[i]*nums[j] % 200003
    result_sum.append(a)
  k+=1
print(sum(result_sum))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
data_pre=input().split()
data=[int(s) for s in data_pre]
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans+=(data[i]*data[j])%200003
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import *
input()
nums = [int(x) for x in stdin.readline().split()]
p = 200003

isMod = []
for num in nums:
    if num % p != 0:
        isMod.append(num)

total = 0
for i in range(len(isMod)):
    for j in range(i+1, len(isMod)):
        total += (isMod[i]*isMod[j] % p)

print(total)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
alis = list(map(int, input().split()))
anslis = []
for i in range(0,n):
  for j in range(0,i):
    if i != j:
      anslis.append((alis[i] * alis[j]) % 200003)
      
print(sum(anslis))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

P = 200003
N = int(input())
li = list(map(int, input().split()))
combi = list(combinations(li,2))
ans = 0
for com in combi:
	ans += com[0] * com[1] % P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
nums=list(map(int, input().split(" ")))

result_sum=0
k=1
for i in range(N):
  for j in range(k, N):
    a = nums[i]*nums[j] % 200003
    result_sum += a
  k+=1
print(result_sum)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
nums=list(input().split(" "))
for i in range(N):
  nums[i]=int(nums[i])
result_sum=0
k=1
for i in range(N):
  for j in range(k, N):
    a = nums[i]*nums[j] % 200003
    result_sum += a
  k+=1
print(result_sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
ans = 0
count = arr.count(0)
while True:
    if 0 in arr:
        arr.remove(0)
    else:
        break
for i in range(n - count):
    for j in range(i + 1, n - count):
        ans += ((arr[i] % 200003) * (arr[j] % 200003)) % 200003
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [i%200003 for i in a]
s = 0
for i in range(n):
	for j in range(i):
		s+=(b[i]*b[j])%200003
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = 200003
b = []
ans = 0
for i in range(n):
    for j in range(1,n - i):
        b.append(a[i]*a[i + j])
for k in range(len(b)):
    ans += b[k] % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
ans = 0
count = 0
while True:
    if 0 in arr:
        arr.remove(0)
        count += 1
    else:
        break
for i in range(n - count):
    for j in range(i + 1, n - count):
        ans += (arr[i] * arr[j]) % 200003
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += (arr[i] * arr[j]) % 200003
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def convolve(a, b):
	n = 1
	n_a, n_b = len(a), len(b)
	while n < n_a + n_b - 1:
		n <<= 1
	A = np.fft.rfft(a, n)
	B = np.fft.rfft(b, n)

	C = A * B
	c = np.fft.irfft(C, n)
	c = np.rint(c).astype(np.int64)

	return c[:n_a + n_b - 1]

p = 200003
n = int(input())
b = list(map(int, input().split()))
a = [0 for _ in range(p-1)]
ref = [0 for _ in range(p)]
po = [0 for _ in range(p-1)]
y = 1
for i in range(p-1):
	ref[y] = i
	po[i] = y
	y = (y * 2) % p
ans = 0
for x in b:
	if x == 0:
		continue
	a[ref[x]] += 1
	ans -= (x*x) % p
conv = convolve(a, a)
for i in range(2*p-3):
	ans += po[i % (p-1)] * conv[i]
print(ans // 2)

Submission status: Accepted

Solution code:
import numpy as np
from numpy.fft import fft
from numpy.fft import ifft
class FFT:
  def exe(s, A, B):
    N, M = 1, len(A) + len(B) - 1
    while N < M: N <<= 1
    A, B = s.arrN(N, A), s.arrN(N, B)
    A = fft(A) * fft(B)
    A = ifft(A).real[:M] + 0.5
    return list(map(int, A))
  def arrN(s, N, L):
    return np.zeros(N) + (L + [0] * (N - len(L)))

N = int(input())
a = list(map(int, input().split()))
MOD = 200003

r = 2
EXP = [0] * MOD
LOG = [0] * MOD
EXP[0] = 1
# r ^ i % MOD = EXP[i]
# logr(i) = LOG[i]
for i in range(1, MOD):
  EXP[i] = EXP[i - 1] * r % MOD
  LOG[EXP[i]] = i

b = [0] * MOD
for n in a:
  # log0は無限、実際には不要なので無視
  if n == 0: continue 
  b[LOG[n]] += 1

# x * y = z => log(x * y) = log(z) => log(x) + log(y) = log(z)
# c[i] <- log(x) + log(y) が i となる個数
f = FFT()
c = f.exe(b, b)

ans = 0
t = 1
for n in c:
  # log(z)をzに戻しつつ個数を掛ける
  ans += n * t
  t = t * r % MOD

# i * i が含まれているので引く
for i in a:
  ans -= i * i % MOD

# i * j と j * i が両方含まれているので割る
ans //= 2

print(ans)