SGU 193. Chinese Girls' Amusement

SGU193 推公式,然后大数。 水题。

193. Chinese Girls’ Amusement

time limit per test: 0.25 sec. memory limit per test: 65536 KB

input: standard output: standard

You must have heard that the Chinese culture is quite different from that of Europe or Russia. So some Chinese habits seem quite unusual or even weird to us. So it is known that there is one popular game of Chinese girls. N girls stand forming a circle and throw a ball to each other. First girl holding a ball throws it to the K-th girl on her left (1 ≤ K ≤ N/2). That girl catches the ball and in turn throws it to the K-th girl on her left, and so on. So the ball is passed from one girl to another until it comes back to the first girl. If for example N = 7 and K = 3, the girls receive the ball in the following order: 1, 4, 7, 3, 6, 2, 5, 1. To make the game even more interesting the girls want to choose K as large as possible, but they want one condition to hold: each girl must own the ball during the game.


Input file contains one integer number N (3 ≤ N ≤ 102000) - the number of Chinese girls taking part in the game.


Output the only number - K that they should choose.

Sample test(s)


Test #1 7 Test #2 6


Test #1 3 Test #2 1

就是找出一个<=N/2的数,使得gcd(k,N) == 1 如果N是奇数,假设N = 2\*p+1, 那么 答案就是p,   gcd(p,2\*p+1) = gcd(p,1) = 1; 如果N是偶数,假设N = 2\*p, 如果p是奇数,p和p-1明显都不满足和N的gcd为1,gcd(p-2,2\*p) = gcd(p-2,4) = 1, 因为4和奇数的gcd为1,所以答案是p-2 如果p是偶数,p不满足,gcd(p-1,2*p) = gcd(p-1,2) = 1 所以答案是p-1  

import java.util.;
import java.math.

public class Solution
public static void main(String []arg){
Scanner cin = new Scanner(;
BigInteger n = cin.nextBigInteger();
else {
BigInteger n2 = n.divide(BigInteger.valueOf(2));
n2 = n2.subtract(BigInteger.ONE);
n2 = n2.subtract(BigInteger.ONE);

------ 本文结束------
  • 本文作者: kuangbin
  • 本文链接: 539.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!