SPOJ.com - Problem SQUA

SQUA_REV - Revenge of the squares

Given a number calculate the product N of their digits bigger than zero. The output is the number R of different (!) presentations of N in the form A*A+B*B with A and B being positive integers including zero.

Input

Twenty tests with one positive integer < 10^20.

Output

Print the illustrated above number R for each test.

Example

Input:
5
7
78185824586267361855

Output:
1
0
3

Submit solution!

Added by:	HWK
Date:	2011-02-25
Time limit:	1.096s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64

hide comments

2011-03-10 12:03:20 HWK
Primary I wrote this task for SHORTEN, i.e. to get small not fast code. It ended up in SPOJ classical accidentally. But there are two variations:
http://www.spoj.pl/problems/SQUAREV1/
http://www.spoj.pl/SHORTEN/problems/SQUAREV/ (You know this task with 100 test cases.)

RE(debanjan):Ok I solved them both but surprisingly even 100 test cases allows semi-brute-force in python.

Last edit: 2011-03-18 06:32:20

2011-03-09 20:46:39 :(){ :|: & };:

@HWK:Agreed,but due to the number of test cases and the size of the input(i.e < 10^20) python and C semi brute-force which is computing the actual multiplication then factorizing is passing very easily,which might be avoided,the idea of this task appears very interesting to me and may be I would make harder version of this in future :-)

Last edit: 2011-03-09 20:51:01

2011-03-08 18:07:55 HWK
I think a smaller time-limit wouldn't change very much. If you don't understand the idea of the task solving in 10 sec. would just as difficult as in 1 sec.

2011-03-07 18:31:24 :(){ :|: & };:

Are you sure you want to give 10 seconds ?

2011-03-02 16:13:14 HWK
So I've changed SQUAREV, SQUAREV1 and EQUASOLV to none hoping the last two will appear in SHORTING too.
SQUA_REV will stay unchanged because solutions are still submitted there. I also won't make a byte limit since the biggest solutions are beyond 2000 Bytes.

Last edit: 2011-03-01 15:11:56

2011-03-02 16:13:14 Piotr KÄ…kol
I'll try to explain everything.
Task have an option called "Placement in main problemset". If task is for shortening You have two options:
1) if You want to add it to main SPOJ tick "challenge", "tutorial" or "partial"
2) if You don't want it to be on main SPOJ (as numerix suggests) tick "none"
In that way shortening task can be either on both SHORTEN and main SPOJ or on one one them.

So You can just untick option "challenge" in task SQUAREV and it will still be on SHORTEN and tick option "classical" in taks SQUA_REV.
Unfortunately, a task can't be in the same time classical and challenge so You rightly made a second task with the same description.

2011-03-02 16:13:14 HWK
This are problems of Piotr Kakol. Maybe he has got more options.

2011-03-02 16:13:14 numerix
There are problems in SHORTEN contest, that come from classical section (e.g. CANTON -> CANTON2) and other problems that don't appear in SPOJ main sections at all (e.g. ROMANCAL). So there must be a way to publish only in SHORTEN.

2011-03-02 16:13:14 HWK
To add a problem in SHORTEN (which was my intention) it seems to be necessary to be in challenge section. A classical problem wouldn't work. (That's the information of Piotr Kakol) So you will be right: Challenge will be more and more a shortening contest.

Last edit: 2011-02-28 10:33:41

2011-03-02 16:13:14 numerix
To me it doesn't matter, if it's in challenge or in classical section. On the other hand there are some new shortening problems in challenge and it should be avoided that challenge becomes too easy or will be more and more a shortening contest. So why not remove the sentence "Could you beat 47 bytes?" and leave it in classical with a restriction on size limit, so that it can be solved in many languages, but has to be in some way optimized according to size.

Last edit: 2011-02-27 17:10:21