NYOJ-歐幾裡得

NYOJ-歐幾裡得

歐幾裡得

描述

已知gcd(a,b)表示a,b的最大公約數。

現在給你一個整數n，你的任務是在區間[1,n)裡面找到一個最大的x，使得gcd(x,n)等於1。

輸入

輸入文件的第一行是一個正整數T，表示有T組測試數據
接下來有T行，每行有一個正整數n (1<=n<=10^1000)。

輸出

每組測試輸出要求x。

樣例輸入

2
4
7

樣例輸出

3
6

代碼:

#include
#include
char a[1001];
int b[1001];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int i,j;
		scanf("%s",a);
		int len=strlen(a);
		if(strcmp(a,"1")==0)
		{
			printf("1\n");
			continue;
		}
		for(i=len-1,j=0;i>=0;--i,++j)
		b[j]=a[i]-'0';
		if(b[0]!=0)
		{
		  b[0]=b[0]-1;
	    }
		else
		{
			b[0]=10-1;
			b[1]--;
			for(i=1;i=0;--i)
		printf("%d",b[i]);
		printf("\n");
		
	}
	return 0;
}

解題思路:

相鄰的的兩個數最大公約數恆為 1,所以1~n中最大的X使得Gcd(x,n)==1,則x=n-1;【注意特列:當n=1時X=1】