john smith - 2 years ago 94
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) .

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 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
``````

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).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download