首页 > 代码库 > 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-欧几里得
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。