john smith - 7 months ago 10

Python Question

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 integerT- denoting the number of test

cases.

Tlines follow each containing two integersA,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

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

Source (Stackoverflow)

Comments