题目来源: http://acm.nyist.net/JudgeOnline/problem.php?pid=976
For any non-empty sequence of positive integers s1, s2, ..., sK their least common multiple is the smallest positive integer that is divisible by each of the given numbers. We will use "lcm" to denote the least common multiple. For example, lcm(3) = 3, lcm(4,6) = 12, and lcm(2,5,7) = 70.
You are given an array S and an integer x. Find out whether we can select some elements from S in such a way that their least common multiple will be precisely x. Formally, we are looking for some s1, s2, ..., sK, K >= 1, such that each si belongs to S, and x=lcm(s1, s2, ..., sK). Return "Possible" if such elements of S exist, and "Impossible" if they don‘t.
4 20 2 3 4 5 3 60 2 3 4
Possible Impossible
分析:
在给定的n 个数中, 先去掉 不能整数 x 的数, 剩下的数 的最小公倍数 恰好 == x, 表示有解。
代码如下:
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<math.h> #include<string.h> #include<string> #include<queue> #include<algorithm> #include<map> using namespace std; vector<int> vk; int gcd(int a, int b){ return b==0?a : gcd(b, a%b); } int lcm(int a, int b){ return b/gcd(a,b) * a; } int main(){ int n , x,temp; while(cin>>n>>x){ vk.clear(); for(int i=0 ;i<n ;i++){ cin>>temp; if(x%temp == 0) vk.push_back(temp); } int lc=1; for(int i=0; i<vk.size(); i++){ lc=lcm(lc, vk[i]); } if(lc == x) printf("Possible\n"); else printf("Impossible\n"); } return 0; }
寻找 n 个数中 k 个数的最小公倍数 x LCMSetEasy,布布扣,bubuko.com
寻找 n 个数中 k 个数的最小公倍数 x LCMSetEasy
原文:http://www.cnblogs.com/zn505119020/p/3606229.html