Prime Cycle
Time limit1sMemory limit128 MB
Simulate a circle of N people where the square-chair holder repeatedly swaps rightward by successive prime counts over K rounds, then report the neighbours of person A, with N up to 5,000,000 and K up to 500,000 requiring an efficient model of the swapping process rather than direct simulation.
- Level
Medium7 of 10
- Topics
- Simulation, Math, Implementation
- Solved
- No attempts yet
Problem
Sanggeun and his friends play the Prime Cycle game. The people are numbered from 1 to N.
Before the game starts, N-1 round chairs and one square chair are arranged in a circle. Person 1 sits on the square chair, and persons 2 through N take the remaining chairs one by one in counter-clockwise order. Everyone faces the centre of the circle.
The game consists of K rounds. At the start of round i, the person sitting on the square chair stands up, shouts "I am the square!", and then swaps seats with the person to their right exactly Pi times, where Pi is the i-th smallest prime.
The following illustrates the case N=5, K=3.
- Round 1:
- Round 2:
- Round 3:
Given N, K, and A, write a program that finds the neighbours of person A after the game ends.
Input
The first line contains N, K, and A separated by spaces. (3 ≤ N ≤ 5,000,000, 1 ≤ K ≤ 500,000, 1 ≤ A ≤ N)
Output
After the game ends, print the person to the right of person A and the person to the left of person A, in that order.