CODEWITHSUNDEEP
pythonmath
sid597
sid597

Reputation: 1019

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

Upvotes: 0

Views: 905

Answers (2)

whd
whd

Reputation: 25

def gcd(a, b):

returns greatest common divisor of a and b'''

return gcd(b % a, a) if a and b else max(a, b)

print test gcd should print 6,5, 7, and 9'''

print gcd(48,18)
print gcd(10,5)
print gcd(14,21)
print gcd (9,0)

Upvotes: 0

freakish
freakish

Reputation: 56587

Writing out the G(a, b) = f(gcd(a, b)) (so that you can use the cited formula) is incorrect since the function is not constant. The proper solution is this:

for i in range(int(raw_input())):
    A, B = map(int, raw_input().split())

    # proper algorithm
    s = 0
    for a in xrange(1, A):
        for b in xrange(1, B):
            s += a * b * G(a, b)
    print s % 1000000007

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

Careful analysis of G might give some optimization insight but it is definitely not a trivial one if any.

Here is a simple optimization:

import fractions

DIVISOR = 1000000007


def is_not_square_free(a):
    counter = 1
    factor = 1
    while factor < a:
        counter += 1
        factor = counter * counter
        if a % factor == 0:
            return True
    return factor == a


def F(n):
    if n == 1:
        return 1
    if is_not_square_free(n):
        return 0
    return n


_CACHE = {}
def G(a, b):
    a = a % DIVISOR
    b = b % DIVISOR
    key = (a, b) if a > b else (b, a)
    if key not in _CACHE:
        _CACHE[key] = (a * b * F(fractions.gcd(a, b))) % DIVISOR
    return _CACHE[key]


def S(A, B):
    s = 0
    for a in range(1, A+1):
        for b in range(1, B+1):
            s += G(a, b)
    return s


for _ in range(int(raw_input())):
    A, B = map(int, raw_input().split())
    print(S(A, B) % DIVISOR)

Upvotes: 1

Related Questions