我是靠谱客的博主 潇洒奇异果,这篇文章主要介绍数论——GCD,现在分享给大家,希望可以做个参考。

ZOJ Problem Set - 3846

题意:

给 N 个数,任取两个数Ai、Aj,求出这两数的GCD,然后用GCD替换这两个数的值。
直至这n个数的值都相等为止,此时输出求GCD的次数,然后按顺序输出每次求GCD的对应的那两个数。
若求GCD的次数超出5*N次时仍未满足停止条件则输出 -1

思路:

只要出现1,就可以将其余的数都变成1,所以,我们从第一个数开始,
GCD(Ai,Ai+1) ,i++;一旦满足GCD(Ai,Ai+1) == 1,便可停止,然后用Ai(或Ai+1)与其他的数做GCD。如此一来求GCD的次数最多不会超过2n-2次。
若i=n-1后仍未出现1,则说明所有数都不会化为相同的数。所以输出 -1

AC代码如下:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream> #include <cstring> #include <algorithm> #include "stdio.h" #include<fstream> using namespace std; #define Max_N 100002 int N; int num[Max_N]; int kgcd(int a, int b) { if (a == 0) return b; if (b == 0) return a; if (!(a & 1) && !(b & 1)) return kgcd(a>>1, b>>1) << 1; else if (!(b & 1)) return kgcd(a, b>>1); else if (!(a & 1)) return kgcd(a>>1, b); else return kgcd(abs(a - b), min(a, b)); } int main() { int times = 0; while(scanf("%d",&N)!=EOF) { bool exist_one = false; int tag = 0; times++; for(int i =0 ; i<N; i++) scanf("%d",&num[i]); for(int i =0; i<N-1; i++) { int temp = kgcd(num[i],num[i+1]); if(temp ==1) { exist_one = true; tag = i+1;//取较小的那个数 break; } num[i] = temp,num[i+1] = temp; } printf("Case %d: ",times); if(exist_one) { printf("%dn",tag+N-2); for(int i = 1; i<=tag; i++) printf("%d %dn",i ,i+1); for(int i = tag; i>1; i--) printf("%d %dn",i-1 ,i); for(int i =tag+1; i<N; i++) printf("%d %dn",i ,i+1); } else { printf("%d",-1); printf("n"); } printf("n"); } }

如有错误,还望指出!
转载请注明出处:http://blog.csdn.net/Big_Heart_C

最后

以上就是潇洒奇异果最近收集整理的关于数论——GCD的全部内容,更多相关数论——GCD内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(78)

评论列表共有 0 条评论

立即
投稿
返回
顶部