We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #211: Divisor Square Sum
Project Euler #211: Divisor Square Sum
Contest ends in
+ 0 comments i didn't get the logic of first test case till now Can u explain it more detailed ?
+ 0 comments Some small hints: 1. Distance for all prime numbers will be 1 2. Squares of all prime numbers
n
will have always 3 divisors: 1, n and n^2
+ 0 comments please help in reducing complexity
or feel free to give any advice
import math def sum_square_divisor(x): sum_num=0 for i in range(1,int(math.sqrt(x))+1): if(x%i==0): if(x/i==i): sum_num+=i*i else: sum_num+=i*i sum_num+=int((x/i))*int((x/i)) return sum_num def isaperfectsquare(x): sr=math.sqrt(x) return ((sr-math.floor(sr))==0) q = int(input()) for i in range(q): arr=list(map(int, input().split())) N=arr[0] K=arr[1] check_list=[] finalsum=0 for n in range(1,N+1): if(n==1): for j in range(K+1): check_pos=n+j check_neg=n-j if(check_neg>0): if(isaperfectsquare(check_pos) or isaperfectsquare(check_neg)): finalsum+=n break else: if(isaperfectsquare(check_pos)): finalsum+=n break else: divisor_sum=sum_square_divisor(n) for j in range(K+1): check_pos=divisor_sum+j check_neg=divisor_sum-j if(check_neg>0): if(isaperfectsquare(check_pos) or isaperfectsquare(check_neg)): finalsum+=n break else: if(isaperfectsquare(check_pos)): finalsum+=n break print(finalsum)
+ 0 comments please help(terminated due to timeout) this code only able to pass test case 0
import math def div(n): return set(x for tup in ([i, n//i] for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup) def sq(l): return [i ** 2 for i in l] def output(n,k): o=[] for i in range(2,n+1,1): n_div=div(i) sq_div=sq(n_div) snds=sum(sq_div) rtsq=math.sqrt(snds) x=math.ceil(rtsq) y=math.floor(rtsq) if(abs((x*x)-snds)<=k or abs((y*y)-snds)<=k): o.append(i) os=sum(o) return os+1 n=int(input()) cont = [] for j in range(n): cont.append(list(map(int, input().rstrip().split()))) for i in range(n): print(output(cont[i][0],cont[i][1]))
+ 0 comments i did not understand: 65 0 :: For the first one, the only integers less than 65 for which sigma2(n) is a square are 1 and 42, hence the answer is 43.
plz. explain.
also give more test case
Load more conversations
Sort 23 Discussions, By:
Please Login in order to post a comment