Page 1 of 2
11245 - Anti-Arithmetic-Sequence
Posted: Sun Jul 29, 2007 6:16 am
by Wei-Ming Chen
I am wondering why wrong answer, can someone check the I/O below?
Input:
Code: Select all
9
5 18
10000 3
100000 3
45214522 9
2000000000 15
111111111 7
417748545 13
10202010 27
2000000000 3
My output
Code: Select all
5
1679657
57476669
112354598
3400966932
484878943
728021160
11857697
301084278403433
Or some stricky I/O? Thanks
Edit: The outputs are correct, but becare of that n might > 2*10^9
Posted: Sun Jul 29, 2007 8:31 am
by pvncad
hi,
For p = 5, i think, sequence should look like
1, 2, 3, 4, 8, 9, 10, 11, 22, 23, 24, 25, 29, ....
But from sample test, answer of n = 10, p = 5 is 12. Am I missing something here ?
Posted: Sun Jul 29, 2007 8:34 am
by emotional blind
for p=5
sequence will be
1, 2, 3, 4, 6, 7, 8, 9, 11, 12, ....
Posted: Sun Jul 29, 2007 8:41 am
by pvncad
thanks. Now, I know what I missed out.
Posted: Sun Jul 29, 2007 8:45 am
by emotional blind
Posted: Sun Jul 29, 2007 8:57 am
by Wei-Ming Chen
yes... it really help
I got Acceped now..
but why... the problem say n<=2000000000...
Posted: Sun Jul 29, 2007 9:00 am
by emotional blind
Wei-Ming Chen wrote:
but why... the problem say n<=2000000000...
What is the problem with that?
Posted: Sun Jul 29, 2007 9:03 am
by Wei-Ming Chen
Oh, I mean that it say
Each case contains 2 integers n (1≤n≤2*10^9) and p (3≤p≤30)
in the problem B (11245)
Posted: Sun Jul 29, 2007 9:05 am
by emotional blind
Posted: Sun Jul 29, 2007 9:18 am
by sclo
I still can't figure out the case when p is not prime.
Posted: Sun Jul 29, 2007 9:20 am
by emotional blind
There is not any case in judge's input where p is not prime.
Posted: Sun Jul 29, 2007 9:23 am
by sclo
shouldn't they say that somewhere in the problem statement? I spent quite a long time on it.
Posted: Sun Jul 29, 2007 9:26 am
by emotional blind
Really, it troubles!!!
Posted: Thu Aug 02, 2007 11:46 pm
by sonyckson
Hello... i have found a kind of pattern and solved the problem... but i would like to know why my solution function... can anyone give some hints to think about?
I dont give the pattern but i suppose the majority have done it in this way... Thanks ! eric.
Posted: Fri Aug 03, 2007 9:50 am
by sclo
sonyckson wrote:Hello... i have found a kind of pattern and solved the problem... but i would like to know why my solution function... can anyone give some hints to think about?
I dont give the pattern but i suppose the majority have done it in this way... Thanks ! eric.
Did you solve the case for p not prime?
If p is prime, then a number theory proof works. It would be a spoiler if I post complete proof here. The key ingredient in the proof is the requirement for gcd(x,p)=1 for any x.
The proof was actually used in the solution of a USAMO 95 problem before.
It was not supposed to be very obvious, but to anyone used to olympiad problems, this should've been easy.
http://www.kalva.demon.co.uk/usa/usoln/usol951.html