NYOJ 145 聰明的小珂

NYOJ 145 聰明的小珂

/*
題目大意：求解和輸入數的互質的數
解題思路：求解和 n 互質的最大數，從n/2開始找

關鍵點：GCD函數的使用
解題人：lingnichong
解題時間：2014-10-04 16:11:55
解題體會：還是不知道為什麼這樣就對了
*/

聰明的小珂

描述

小珂是一個愛美的女孩，她有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

輸入第一行有一個整數 0輸出輸出m個k的值

樣例輸入

227

樣例輸出

13

#include
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}    
int main()
{
    int m,n,i;
    scanf("%d",&m); 
    while(m--)
    {
        scanf("%d",&n);
        for(i=n/2;i>0;i--)
        {
            if(gcd(n,i)==1)
            {
            	printf("%d\n",i);
             	break;//跳出是有條件的 
         	}   	
        }    
    }    
    return 0;
}