11245 - Anti-Arithmetic-Sequence

Wei-Ming Chen · Post by **Wei-Ming Chen** » Sun Jul 29, 2007 6:16 am

I am wondering why wrong answer, can someone check the I/O below?

Input:

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

pvncad · Post by **pvncad** » Sun Jul 29, 2007 8:31 am

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 ?

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 8:34 am

for p=5

sequence will be
1, 2, 3, 4, 6, 7, 8, 9, 11, 12, ....

pvncad · Post by **pvncad** » Sun Jul 29, 2007 8:41 am

thanks. Now, I know what I missed out.

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 8:45 am

http://online-judge.uva.es/board/viewtopic.php?t=19742

this may also help you.

Wei-Ming Chen · Post by **Wei-Ming Chen** » Sun Jul 29, 2007 8:57 am

yes... it really help

I got Acceped now..

but why... the problem say n<=2000000000...

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 9:00 am

Wei-Ming Chen wrote: but why... the problem say n<=2000000000...

What is the problem with that?

Wei-Ming Chen · Post by **Wei-Ming Chen** » Sun Jul 29, 2007 9:03 am

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)

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 9:05 am

this topic is discussed here
http://online-judge.uva.es/board/viewtopic.php?t=19742

sclo · Post by **sclo** » Sun Jul 29, 2007 9:18 am

I still can't figure out the case when p is not prime.

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 9:20 am

There is not any case in judge's input where p is not prime.

sclo · Post by **sclo** » Sun Jul 29, 2007 9:23 am

shouldn't they say that somewhere in the problem statement? I spent quite a long time on it.

emotional blind · Post by **emotional blind** » Sun Jul 29, 2007 9:26 am

Really, it troubles!!!

sonyckson · Post by **sonyckson** » Thu Aug 02, 2007 11:46 pm

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.

sclo · Post by **sclo** » Fri Aug 03, 2007 9:50 am

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