首页 > 其他 > 详细

寻找 n 个数中 k 个数的最小公倍数 x LCMSetEasy

时间:2014-03-18 12:11:49      阅读:465      评论:0      收藏:0      [点我收藏+]

题目来源: http://acm.nyist.net/JudgeOnline/problem.php?pid=976

LCMSetEasy

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

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.

 

 
输入
There are multiple test cases.
Each test case contains two lines.The first line is two integer N(1≤N≤100,represents the array contains N integers) and x(1≤x≤10^9). The second line contains N integers,the ith integer represents si(1≤si≤10^9).
输出
Printf "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, 表示有解。
代码如下:
bubuko.com,布布扣
#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;
}
bubuko.com,布布扣

 

寻找 n 个数中 k 个数的最小公倍数 x LCMSetEasy,布布扣,bubuko.com

寻找 n 个数中 k 个数的最小公倍数 x LCMSetEasy

原文:http://www.cnblogs.com/zn505119020/p/3606229.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!