brute force will be TLE for 3rd one …

I mean square-root brute.

then please tell me efficient approach or what modification can i do ?

No idea. It took 1 hour to understand C . They could have written it in simple manner also. I don’t like too much math stuff, so no idea.

It can be used in this case. My solution

Someone use euler sieve other use prime sieve then i don’t know what he/she did?
OK @samarthtandon can u help?

Brute force would time out… Here’s my solution

Editorial is out on cf…

Ok, i will see thanks,
@sarodesparsh don’t mind i can’t understand your code…

I only passes the small one…not full so no idea…
as 1st can be easily done with sieve

if you know the number of factors of N:
if N is even than -> no of even factors = no of factors of N/2
no of odd factors = no of factors of N - even
if N is odd than-> even = 0, odd = factor of N
1 Like

I already pass test 1 , but i want sol . which passes all the test cases

I will try to explain as much as possible:

Basic idea:

Given L and R, iterate from 1 to {\sqrt{R}}
For each {i} in range ({1, \sqrt{R}}):
find all find all multiples of {i} in range({L,R}) and update it in OddList and EvenList.
Then iterate from L to R to find how many have abs(odd - even <= 2)

By OddList I mean, an array of size {R-L+1} where {OddList[i]} represents how many odd multiples the number {L+i} has.

My solution to problem B :-

Apply Gaussian to the 2nd equation and you are done…to check if solution exists or not.

Where to learn about gaussian and diophantine?

Solution to problem C(Street Checker) :

Diophantine takes integer values for all unknowns, but the value of x(according to the equation in the picture) can be decimal value.
So I guess it wont be Diophantine.
Correct me if I am wrong.
And can you provide the code for the second question’s solution?

I am talking about Gaussian…Diophantine was a mis-spell. Yes, I have the AC code. Will post it tomorrow.

1 Like

I solved Q1 using Union Find.

class Dset:
def __init__(self,n):
self.sets=[i for i in range(n)]
self.distinct_sets=n
self.size=[1 for i in range(n)]

def union(self,x,y):
size=self.size
sets=self.sets
px=self.find(x)
py=self.find(y)
if px==py:
return 0

self.distinct_sets-=1
if size[px] > size[py]:
sets[py]=px
size[px]+=size[py]
else:
sets[px]=py
size[py]+=size[px]
return 1

def find(self,x):
sets=self.sets
while sets[x]!=x:
sets[x]=sets[sets[x]]

x=sets[x]
return x
for t in range(int(input())):
n,m=list(map(int,input().split()))
s=Dset(n+1)
ans=0
for __ in range(m):
a,b=list(map(int,input().split()))
ans+=s.union(a,b)
dis=s.distinct_sets
dis-=2
ans+=dis*2
print("Case #{}: {}".format(t+1,ans))