在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
Mashmokh and Numbers
It's holiday. Mashmokh and his boss, Bimokh, are playing a game invented by Mashmokh. In this game Mashmokh writes sequence of n distinct integers on the board. Then Bimokh makes several (possibly zero) moves. On the first move he removes the first and the second integer from from the board, on the second move he removes the first and the second integer of the remaining sequence from the board, and so on. Bimokh stops when the board contains less than two numbers. When Bimokh removes numbers x and yfrom the board, he gets gcd(x, y) points. At the beginning of the game Bimokh has zero points. Mashmokh wants to win in the game. For this reason he wants his boss to get exactly k points in total. But the guy doesn't know how choose the initial sequence in the right way. Please, help him. Find n distinct integers a1, a2, ..., an such that his boss will score exactly k points. Also Mashmokh can't memorize too huge numbers. Therefore each of these integers must be at most 109. Input
The first line of input contains two space-separated integers n, k (1 ≤ n ≤ 105; 0 ≤ k ≤ 108). Output
If such sequence doesn't exist output -1 otherwise output n distinct space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).
Sample test(s)
input
5 2 output
1 2 3 4 5 input
5 3 output
2 4 3 7 1 input
7 2 output
-1
题意:找出一组数列,满足每相邻的两个数的最大公因数和为给定的值。 sl:无以言状的水题,最终挂了,为什么呢,我把最后一个数字写的太小了。在知道直接0走起。 相邻两个数字互素。利用这点很容易求出答案。
1 #include<cstdio>
2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 typedef long long LL; 7 const int MAX = 200; 8 int main() 9 { 10 int n,k; 11 while(scanf("%d %d",&n,&k)==2) 12 { 13 if(n==1&&k!=0) printf("-1\n"); 14 else if(n==1&&k==0) printf("1\n"); 15 else if(n/2>k) printf("-1\n"); 16 else 17 { 18 int a=1,b=2; 19 int t=n/2; t*=2; int x=n/2; 20 int last=k-(x-1); 21 for(int i=1;i<x;i++) 22 { 23 if(a!=last&&b!=last&&a!=2*last&&b!=2*last) 24 { 25 if(i==1) printf("%d %d",a,b),a+=2, b+=2; 26 else printf(" %d %d",a,b),a+=2, b+=2; 27 } 28 else 29 { 30 while(a==last||b==last||a==2*last||b==2*last) 31 a+=2, b+=2; 32 if(i==1) printf("%d %d",a,b),a+=2, b+=2; 33 else printf(" %d %d",a,b),a+=2, b+=2; 34 35 } 36 } 37 if(x!=1&&last!=1) printf(" %d %d",2*last,last); 38 else if(last!=1&&x==1) printf("%d %d",2*last,last); 39 else if(x!=1&&last==1) printf(" 99999997 99999998"); 40 else if(last==1&&x==1) printf("99999997 99999998"); 41 if(n%2) printf(" 1000000000"); 42 printf("\n"); 43 } 44 } 45 return 0; 46 }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论