17110 Divisible
时间限制:1000MS 内存限制:65535K
题型: 编程题 语言: 无限制
Description
Given n + m integers, I1,I2,...,In,T1,T2,...,Tm, we want to know whether (I1*I2*...*In)%(T1*T2*...*Tm)= =0.
输入格式
The first line gives two integers n and m. 1<=n,m<=100
The second line gives n integers I1 I2 ... In.
The third line gives m integers T1 T2 ... Tn.
1<=Ii, Ti<=231
输出格式
Satisfy (I1*I2*...*In)%(T1*T2*...*Tm)= =0, output "yes", otherwise output "no"
输入样例
2 3
24 14
2 7 3
输出样例
yes
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll I[],T[]; ll gcd(ll a,ll b)
{
return b==?a:gcd(b,a%b);
} int main()
{
int n, m;
cin>>n>>m;
for(int i = ; i < n; ++i) {
cin>>I[i];
}
for(int i = ; i < m; ++i) {
cin>>T[i];
} int i;
for(i = ;i < m ; i++){
for(int j = ; j < n && T[i] != ; j++){
if(I[i]==) continue;
ll g=gcd(I[j],T[i]);
I[j] /= g;
T[i] /= g;
}
if(T[i] != ) break;//发现一个T[i]不能被I[0]*I[1]*…*I[n]整除,则跳出循环输出no
}
if(i < m) cout<<"no";
else cout<<"yes";
return ;
}