简单第一个数论
有一堆数,问你能否从中选出若干个数使得这些数的最小公倍数为x
思路:求出数组中能被x整除的数字的最小公倍数lcm,如果lcm%x==0,则可以找到,否则找不到。
#include <iostream> #include <cstdio> #include <cmath> #include <vector> using namespace std; typedef long long ll; vector<int>p; int n; int a[55]; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int main() { cin >> n; for(int i=1;i<=n;i++) { cin >> a[i]; } ll x; cin >> x; ll res =1; for(int i=1;i<=n;i++) { if(x%a[i]==0) { res = res * a[i] / gcd(res,a[i]); } } if(res%x==0) { cout <<"Possible"<<endl; } else{ cout <<"Impossible"<<endl; } return 0; }