nyoj 145 聪明的小珂

                                                                聪明的小珂

    小珂是一个爱美的女孩，她有n条新项链，标号从1到n，每一条项链在颜色上都会有一些差别，n条项链依次摆放，围成一个圈。小珂每次都会从上一次选择项链的位置开始数到第k条项链，把这条项链作为今天要带的项链，每次数的方向都是一致的，现在希望你帮小珂计算出一个最大的k，满足k<=n/2的同时，使得小珂在接下来的n天中将所有的项链都刚好带了一遍。

例如 n=7，取k=3

天数  项链编号

1                      1

2                      4

3                      7

4                      3

5                      6

6                      2

7                      5

227样例输出
13
分析：
打表出来前12个数据。
n   k
3    14    15    26    17    38    39    410  311  512   5
可以发现结果和输入互质AC代码如下：
#include<cstdio>int n;int gcd(int a){       //辗转相除找最大公约数 	int temp=n;	while(a){		int r=temp%a;		temp=a;		a=r;    }	return temp;}int main(){	int m;	scanf("%d",&m);	while(m--){		scanf("%d",&n);		for(int k=n/2;k>0;k--){			if(gcd(k)==1){				PRintf("%d/n",k);				break;			}		}			}	return 0;}