PYTRIP2 - Pythagorean triples (medium)
Pythagoras is credited, by tradition, for the first proof of the relation a2 + b2 = c2 in any right angled triangle where c is hypotenuse and a and b are the catheti.
We define a Pythagorean triple as a set of three positive integers a, b, and c which satisfy the above equation , ie ,
a2 + b2 = c2.
{3,4,5} is the most common example of such triples.
Input
The first line of input contains an integer T, the number of test cases.
Each of the next T lines contains two integers N, M.
Output
For each test case, print on a single line the number of Pythagorean triplet {a,b,c} such that N ≤ a,b,c ≤ M.
Example
Input: 3 1 5 4 10 10 100 Output: 1 1 45
Constraints
0 < T < 100 0 < N < M 0 < T × M < 1.21×10^8
There are several input files. Time limit is ×20 my top speed with C language (1kB of code). For your information, my total best time is 0.59s for the 6 input files. (Edit 2017-02-11, after compiler changes). Warning, it could be hard with interpreted languages. You can try before the quite similar tutorial problem : PYTRIP before.
Information
This problem is part of the Bubble Cup competition qualification round (April 2014). @students: good luck. GNU_salutations.
hide comments
|
Vukasin:
2014-04-04 17:46:29
Can someone explain me how the input into my program is done? How server enters data into my program? I obviously have problem with that(I use scanf). Is scanf right choice, im writing in C programming language. Thanks!
|
|
Tomislav Gudlek:
2014-04-03 03:45:49
Dudes. Even if you're solving problems together for Bubble Cup qualification round, there's no reason for submitting the same code here on SPOJ. A single user submitting is sufficient for getting credit. |
|
Aleksandar Kahriman:
2014-04-02 23:04:57
Hi Francky, I understand your frustration, but please allow us to submit. There aren't too many teams anyway, so it shouldn't be a problem for you to manually ban people that are abusing the system (not that you should be wasting your time on that, but this is a rather big deal for the people who have spent a lot of time on this). Me and my team have spent around 6 hours on your problem, and the submit button vanished when we were about to submit our final solution. Hope you will reconsider,
|
|
Filip:
2014-04-02 23:04:57
@Francky bubblecup.org BubbleCup is competition by MDCS(Microsoft Development Center Serbia) and this is first quals for final. Every year they choose randomly SPOJ problems for qual. Do you want to make problem for all contestants and organizers? Please remove your problem from SPOJ if you doesn't want to anybody solve it. We have solved correctly this problem. |
|
Francky:
2014-04-02 23:04:57
I didn't knew about this competition, it could have been fine if organizer send me a message. If my problem suit well for that task, I'm quite happy. But I'm not allowing copy/paste submissions for this problem (one team -> one account) ; there were some troubles. Moreover, I prefer that this 'competition' hosts it's own data and judge. So my problem will be unavailable until the end of this 'competition'. Thanks for your comprehension. |
|
popina:
2014-04-02 23:04:57
WE WANT SUBMIT BUTTON BACK!
|
|
|
Filip:
2014-04-02 23:04:57
@Francky, are you ok?
|
|
|
Francky:
2014-04-02 23:04:57
Submissions disallowed for a while. There's a pollution with some copy/paste solution. Filip : don't try to insist anymore. Please be respectful for users who earn points.
|
| Added by: | Francky |
| Date: | 2013-04-11 |
| Time limit: | 1s-3.400s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
RSS