注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1212.分式凑整  

2011-12-03 10:12:50|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1212.分式凑整
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 167 (42 users)         Accepted: 39 (32 users)
[ My Solution ]

Description

        某天,一个朋友拿了个问题来找zzz帮忙解决,可是zzz最近正忙着期末的各科考试。zzz既想自己能好好复习,又想帮帮这位朋友,因此他就把这个问题拿来找人帮忙。   

        给定一组正整数,要求选一些数字(不能不选),并把它们的积作为分母,其余数字的积作为分子,问是否存在某种选择,使得构成的分式可以约分为一个整数呢?例如,{15,35,14,6},如果选取6*35的积作为分,15*14的积作为分子,则结果正好为整数。

Input

第一行输入一个正整数T,(1<=T<=100),表示有T组测试数据;
接下来每组数据首先输入一个正整数n(2<=n<=5000),表示该组测试数据中有n个正整数;
然后接着一行输入n个正整数a,(1<=a<=32767)。

Output

每组数据输出一行,如果存在某种选择,使得构成的分式能约分成整数,则输出”Yes”,否则输出”No”。

Sample Input

1
4
15 35 14 6

Sample Output

Yes

Source
 
只要扫描每一个a[i],剩下的a[j]和a[i]求最大公约数,一直到a[i]为1就可以计算出是不是可以被整除了。
#include <stdio.h>
inline int gcd(int a,int b)
{
 return b?gcd(b,a%b):a;
}
int main()
{
 int t;
 scanf("%d", &t);
 while(t--)
 {
  int n, a[5001], i, j;
  scanf("%d", &n);
  for(i = 0; i < n;i++)
   scanf("%d", &a[i]);
  int p, flag = 1;
  for(i = 0; i < n && flag; i++)
  {
   p = a[i];
   for(j = 0; j < n; j++)
   {
    if(i != j)
    {
     p = p / (gcd(p, a[j]));
     if(p == 1){flag = 0;break;}
    }
   }   
  }
  if(!flag) printf("Yes\n");
  else printf("No\n");
 }
return 0;
}
  评论这张
 
阅读(83)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017