10831 - Gerg's Cake

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

10831 - Gerg's Cake

Post by Eduard » Tue Mar 22, 2005 3:53 pm

Can somebody give hint how to solve this poblem?
Thanks
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Mar 22, 2005 4:31 pm

Quadratic residues and Legendre's/Jacobi's symbols.

You can assume that integer p is always either a prime (including 2), or unity -- this follows from the first paragraph.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Mar 22, 2005 4:58 pm

Here are my inputs and outputs, is there anything wrong?

Code: Select all

1 3
1024 17
2 101
0 1
3000000000 5
15 11
721761 7
115 2
6137 2
4 2
0 2
-1 -1

Code: Select all

Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Mar 22, 2005 5:49 pm

Your output is correct except for the case "3000000000 5". 3000000000 is congruent to 0 (mod 5), and zero is a quadratic residue modulo 5, so the answer for that case should be "Yes".

Before evaluating Legendre symbol in this problem, you should first reduce the value of a modulo p.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Mar 22, 2005 6:44 pm

Thanks, that was what I was looking for.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Sep 20, 2005 9:04 pm

Hello!

Only one question?

Could anyone say me what is wrong in my code?

Code: Select all

#include <iostream>
using namespace std;

main ()
{
    long long a, p, x, sq;
    
    while (cin >> a >> p && (a!=-1 || p!=-1))
    {
        x=a%p;
        sq=0;
        while (sq*sq<x) sq++;
        if (sq*sq==x) cout << "Yes\n";
        else cout << "No\n";
    }
}
Any test cases will be appreciated.

Thnaks!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Sep 21, 2005 3:58 am

Here are some test cases. My program prints "Yes" to all of them.

Code: Select all

2 7
9 7
16 7
3 11
5 11
31337 2147483629
2147483628 2147483629
-1 -1

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Sep 26, 2005 12:46 am

Hello and thanks mf!

I have used Legendre's symbol, and get correct output for all the input of this thread.
Maybe I haven't computed right Legendre's symbol.
If someone can explain me a bit how have computed this to solve the problem, I will be happy :D

By other hand I have here some test cases, if someone can say if the output is correct I will be happy too

input:

Code: Select all

2 7 
9 7 
16 7 
3 11 
5 11 
31337 2147483629 
2147483628 2147483629 
1 3 
1024 17 
2 101 
0 1
300000000 5
15 11 
721761 7 
115 2 
6137 2 
4 2 
0 2 
3 2
5 2
2 3
2 5
2 2
234 23
234 31
485940 101
2384 101
3843 101
3848 41
3848 31
48885557 31
31 41
347583495 7
23477767 23
347823 101
3478234 2147483629 
115 3
115 2
3478293 17
2348884 19
1234123 17
1234123 19
1234123 23
-1 -1
output:

Code: Select all

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Mon Sep 26, 2005 2:35 am

Emilio wrote:Hello and thanks mf!

I have used Legendre's symbol, and get correct output for all the input of this thread.
Maybe I haven't computed right Legendre's symbol.
If someone can explain me a bit how have computed this to solve the problem, I will be happy :D

By other hand I have here some test cases, if someone can say if the output is correct I will be happy too
The answer for a=31, b=41 should be Yes. (32nd case)

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Sep 26, 2005 8:56 pm

Thanks Martin Macko!

I got AC.

I had a small bug at my algorithm. But one question, I have obtained a time of 0:00.535, and most of solvers have obtained a time about 0:00.030 or smaller, I would like know the method used. I used a method that is about Legendre's symbol and law of quadratic reciprocity, in this method I must break down a number in his prime numbers, and make transformations to obtain trivial cases that I can solve directly.

Any other hint or method will be highly-regarded. :wink:

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Sep 26, 2005 10:00 pm

Legendre symbol can be computed as a^((p-1)/2) (mod p). It's just modular exponentiation.
My 0.002s solution is based on an algorithm from http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf page 27, algorithm #2.149.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Sep 27, 2005 12:16 am

Thanks mf another time!

A good link :wink:

Now, I have solved it at time of 0:00.004

Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

Re: 10831 - Gerg’s Cake

Post by Masum » Fri Nov 30, 2012 4:32 pm

Posted an ac code. So deleted.
Last edited by Masum on Fri Dec 27, 2013 3:24 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10831 - Gerg’s Cake

Post by brianfry713 » Sat Dec 08, 2012 6:06 am

That is AC code and input 31 41 should output Yes
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 108 (10800-10899)”