首页 > 代码库 > NYOJ-欧几里得

NYOJ-欧几里得

欧几里得

时间限制:1000 ms  |  内存限制:65535 KB
难度:0
描述

已知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<stdio.h>
#include<string.h>
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<len;++i)
			{
			  if(b[i]<0)	
			  {
			  	b[i]=b[i]+10;
			  	b[i+1]--;
			  }
			  else
			  break;
			}
		}
		if(b[len-1]==0)
		len--;
		for(i=len-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】

NYOJ-欧几里得