john smith john smith - 7 months ago 10
Python Question

GCD implementation in python

I am solving this problem in SPOJ and it states that :


Problem statement is simple. Given A and B you need to calculate
S(A,B) .

enter image description here

Here, f(n)=n, if n is square free otherwise 0. Also f(1)=1.

Input

The first line contains one integer T - denoting the number of test
cases.

T lines follow each containing two integers A,B.

Output

For each testcase output the value of S(A,B) mod 1000000007 in a
single line.

Constraints

`T <= 1000
1 <= A,B <= 1000000`


Example

Input:
3
42 18
35 1
20 25


Output:
306395
630
128819



I wrote this code for this problem (if I got the the problem right) :

def gcd(a,b): #gcd(a,b)
if b==0:
return a
else:
return gcd(b,a%b)
# print gcd(42,18)

import math
def issquarefree(n): #sqare free number check
i=2
s=i*i
if (n==1 or n==2) or n==3:
return True
while s<=n:
if n%s==0:
i=-1
break
else:
i+=1
s=i*i
if i==-1:return False
else:
return True
for i in range(int(raw_input())): #main program
a,b=map(int,raw_input().split())
g=gcd(a,b)
sa=(a*(a+1))/2 #see below
sb=(b*(b+1))/2 #see below
gc=issquarefree(g)
s=0
if gc== False:
print 0
elif gc==True:
s+=sa*sb*g
print s%1000000007


here I found that enter image description here so applying this to the problem # S(A,B) I wrote this as (multiplication of sum of first A and B numbers ) multiplied by f(n) which is gcd(a,b) or 0.

But I am not getting the expected output to this problem so is my code wrong or I got the problem wrong

my output vs expected

3
35 1
42 18
20 25
630 630
926478 306395
341250 128819

Answer

Your entire approach to the problem is wrong. Here's what you've implemented

sum( a*(a+1)/2 + b*(b+1)/2 + G(a, b) )

where

G(a, b) = f(gcd(a, b))

This is incorrect, I don't even know where did that a*(a+1)/2 came from. And where did double suming disappeared? The proper solution is this:

# Load the data
A = []
B = []
for i in range(int(raw_input())):
    a, b = map(int, raw_input().split())
    A.append(a)
    B.append(b)

# proper algorithm
s = 0
for a in A:
   for b in B:
       s += a * b * G(a, b)

You obviously have to implement G function properly (as returning 0 or gcd(a, b)).

I don't think it can be optimized further because G function cannot be ruled out (or at least I don't see any simple way to do that).

Comments