CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • All Contests
    • June Long 2012
    • May Cook-Off
    • May Long 2012
  • DISCUSS
    • Forums
    • Blog
    • Wiki
    • Facebook
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host your Contest
    • User Groups
    • CodeChef TechTalks
    • All Educational Initiatives
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Tutorials
    • Long Contest Ranks
    • Short Contest Ranks
    • Event Calendar
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home » Compete » July 2010 » Adding Least Common Multiples

Adding Least Common Multiples

Problem code: LCM

  • All Submissions

All submissions for this problem are available.

Given A and B, compute the sum of lcm(a, b) over all pairs of positive integers a and b such that:

(1) a<=A and b<=B.
(2) There is no integer n>1 such that n2 divides both a and b.

Give your answer modulo 230.

Input

The first line contains the number of test cases, t (about 200). Each of the next t lines contains two space-separated integers A and B (1<=A, B<=4000000).

Output

Print the answer to each test case on a separate line.

Example

Input:

4
2 4
3 3
6 5
8 3

Output:

24
28
233
178


Author: MichaelD
Date Added: 6-05-2010
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


  • Submit

Comments

  • Login or Register to post a comment.

output for 6 5 should be 237

Ankit.Sablok19 @ 1 Jul 2010 08:04 PM

output for 6 5 should be 237

@Ankit Sablok Output is

anton_lunyov @ 1 Jul 2010 08:47 PM

@Ankit Sablok

Output is correct.

You forget to delete the pair (4,4).

I had a working solution to

r00t @ 1 Jul 2010 11:05 PM

I had a working solution to this problem since so much time but its just giving me this freaking error

Runtime Error (Other)

I m using python and It satisfies everything !!!!!!!!!!!

Common man , i m r00t, so work !!!!

And Yes its so stupid to

r00t @ 1 Jul 2010 11:10 PM

And Yes

its so stupid to write this way : 1<=A, B<=4000000

Dont u think its a pun ???

It conveys two things

1: A and B lie in  integers b/w 1 and 4 * pow(10,6)   (inclusive)

2: A>=1 without upperbound, B is possitive with a upper bound of 4 x 10^6

What's the meaning of 'Source

bhathiya @ 1 Jul 2010 11:13 PM

What's the meaning of 'Source limit'?

What's the meaning of

bhathiya @ 1 Jul 2010 11:31 PM

What's the meaning of this...? "Give your answer modulo 230"

@Bhathiya Jayasekara: It

DevGeeK @ 2 Jul 2010 04:42 AM

@Bhathiya Jayasekara:

It means that you should divide the result by 230 and output the remainder.

@Antoyn I have successfully

Ankit.Sablok19 @ 2 Jul 2010 08:51 AM

@Antoyn I have successfully deleted that pair and still get 237

@ Aleksandar Stankovski

bhathiya @ 2 Jul 2010 10:05 AM

@ Aleksandar Stankovski

thanks, and please tell me what does it mean by source limit is 50000?

@Ankit Sablok even i am

anurag11 @ 2 Jul 2010 10:18 AM

@Ankit Sablok

even i am getting 237 for that test case

@Akshay - 1 <= A, B <=

triplem @ 2 Jul 2010 10:40 AM

@Akshay - 1 <= A, B <= 4000000 means 1 <= A <= 4000000 and 1 <= B <= 4000000, and is used very commonly.

@Bhathiya - source limit is the maximum size of your source code.

@Ankit, Anurag - The sample output is correct. That is all you need to know.

@Stephen-made a stupid

anurag11 @ 2 Jul 2010 11:03 AM

@Stephen-made a stupid mistake.i finally got 233.thnx anyways

@Stephen- can you tell me one

anurag11 @ 2 Jul 2010 11:27 AM

@Stephen-

can you tell me one thing..When i get a TLE can i be sure that my code gave the right answer?

FAQ

triplem @ 2 Jul 2010 12:19 PM

FAQ

@Stephen- thnx

anurag11 @ 2 Jul 2010 12:30 PM

@Stephen-

thnx

my code gives the right

r_cajetan @ 2 Jul 2010 12:55 PM

my code gives the right answer for the sample input, but wrong answer here...But atleast im not getting a timeout....gotta find that problematic case.....

When i submitted my program

anshusaurav @ 2 Jul 2010 04:52 PM

When i submitted my program it gives internal error. What that means ??

mine too.. internal error???

bhathiya @ 2 Jul 2010 04:59 PM

mine too.. internal error???

and i checked in forums admin

anshusaurav @ 2 Jul 2010 05:02 PM

and i checked in forums admin said check out ur recent submissions for correct status of your submissions but there is nothing in "my submissions " neither in recent sctivity in main page..

please take a look at it admins.

thanks

its ok now its giving TLE

anshusaurav @ 2 Jul 2010 05:03 PM

its ok now its giving TLE

my coide is ok in my machine

jimmycool @ 2 Jul 2010 06:11 PM

my coide is ok in my machine but its giving a time out error

is 2 seconds the total time

bcloud @ 3 Jul 2010 11:56 AM

is 2 seconds the total time for 200 cases?

Yes. FAQ

triplem @ 3 Jul 2010 12:27 PM

Yes. FAQ

in above problem is A always

rajul884 @ 3 Jul 2010 12:32 PM

in above problem is A always less than B or not?

getting TLE...

urbaddy @ 3 Jul 2010 04:41 PM

getting TLE...

There is no integer n>1 such

urbaddy @ 3 Jul 2010 04:41 PM

There is no integer n>1 such that n2 divides both a and b.

 

cud not understand above point..can anyone explain plz.

i uploaded exactly same

seraph @ 3 Jul 2010 05:45 PM

i uploaded exactly same code(which was running on my machine) twice ........once it gave compilation error.............the other time it gave TLE..........how is it possible......your compilers has some bugs ? ........i didn't even open the file b/w the two successive uploads...

can i know how much time

iterbibek @ 4 Jul 2010 02:41 AM

can i know how much time theprogram  takes......

bcoz i hv submitted the code but its showing time exceeded

what is the meaning of there

Najmuzzaman @ 4 Jul 2010 09:41 PM

what is the meaning of there is no integer n>1 such that n2 divides both a and b.

Which part of that sentence

triplem @ 5 Jul 2010 02:58 AM

Which part of that sentence don't you understand?

@ADMIN yes, this is

foofoo @ 5 Jul 2010 08:23 PM

@ADMIN

yes, this is confusing? what is n?

is it one of a or b ? is it the lcms which we are adding? i think someone should answer that question ?

my bad got it now ..sorry,

foofoo @ 5 Jul 2010 08:39 PM

my bad got it now ..sorry, should have read carefully.. the second comment makes it clear

i am getting :( internal

933P @ 5 Jul 2010 11:17 PM

i am getting :( internal server error..

and also, i am using php

and doing get_file_contents("in,txt")

is it ok to do so on codechef?

else how would i take input using php?

and finally, i am storing result in out.txt

if i am wrong somewhere please tell me immediately coz i got working code.

no matter what, i keep

933P @ 6 Jul 2010 08:58 AM

no matter what, i keep getting internal server error. why?

and @ Team Cyclone, why do you post code?

its disgusting to see other's code.

is the time limit(2 seconds)

dwrakh @ 6 Jul 2010 03:53 PM

is the time limit(2 seconds) for a single test case or for all the test cases together?

we are not able to get your

DRSV @ 6 Jul 2010 09:40 PM

we are not able to get your view exactly.........

what are A and B in the problem........

What is n here?? n2 does not

uniquecode @ 8 Jul 2010 12:36 PM

What is n here?? n2 does not divide a and b is ok.. but what is the range of n and what exactly it is??

n is any integer greater than

triplem @ 8 Jul 2010 01:06 PM

n is any integer greater than 1, as the problem statement says.

After submission I have got

oronno @ 8 Jul 2010 01:52 PM

After submission I have got an error

/sources/tested.cpp:1: error: expected unqualified-id before numeric constant

what is it mean?

I did not get any error when I compiled in eclipse(helios) using mingw32-g++

A lot of confusion with

uniquecode @ 9 Jul 2010 02:49 PM

A lot of confusion with n..

1st test case of example..

Suppose, i choose (2,3) pair, and let n=6

then n2 divides both 2 and 3.. ?? what is the range of n(i know it is greater than 1) but less than what??

Please correct me..

 

36 is not a divisor of 2 or

triplem @ 9 Jul 2010 02:52 PM

36 is not a divisor of 2 or 3.

got it!thanks..

uniquecode @ 9 Jul 2010 03:02 PM

got it!thanks..

i downloaded some solutions,

nitin_surana @ 12 Jul 2010 06:05 PM

i downloaded some solutions, but they are giving different outputs with same input. Moreover, two or more solutions don't even give the same result....can anyone explain??/

and even when i give the test

nitin_surana @ 12 Jul 2010 06:07 PM

and even when i give the test cases given here, the output is much greater then given here, about 6-8 digits per output.

@nitin surana The code

Sanji @ 14 Jul 2010 03:10 PM

@nitin surana

The code submitted by Aswin Akhilesh is actually correct. Probably your compiler is not treating SUM[0]=0. So if its not treating that way, just make SUM[0] explicitly equal to 0 under calculateSUM() of Aswin Akhilesh's code.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

Programming Competition Fetching successful submissions
Directi Go for Gold
CodeChef is a global programming communityCodeChef hosts online programming competitions
CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com