时间限制:1000MS 内存限制:65535K
题型: 编程题 语言: 无限制
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> using namespace std; typedef long long ll; ll I[110],T[110]; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int main() { int m,n,i,j; cin>>n>>m; for(i=0;i<n;i++) cin>>I[i]; for(i=0;i<m;i++) cin>>T[i]; for(i=0;i<m;i++) { for(j=0;j<n&&T[i]!=1;j++) { if(I[i]==1) continue; ll tmp=gcd(I[j],T[i]); I[j]/=tmp; T[i]/=tmp; } if(T[i]!=1) break;//发现一个T[i]不能被I[0]*I[1]*…*I[n]整除,则跳出循环输出no } if(i<m) cout<<"no"; else cout<<"yes"; return 0; }
原文：http://www.cnblogs.com/zyx1314/p/3553049.html