首页 > 代码库 > HDU 5512 题解
HDU 5512 题解
题意:给出n,再给出集合A中的两个整数j,k且j≠k,集合满足条件
若j,k∈A,j≠k,且1<=j-k<=n,则j-k∈A;
若j,k∈A,j≠k,且1<=j+k<=n,则j+k∈A;
若集合A中有偶数个数,则输出Iaka;若集合A中有奇数个数,则输出Yuwgna.
2<=N<=20000.共1~500组数据,1000MS
算法/思路:由于减法的存在,可由辗转相除法知道gcd(i,j)在集合中,进而至少有2*gcd(i,j)在集合中,借此可以得知gcd(i,j)的n以内的倍数都在集合A中,且集合A中的数显然都是gcd(i,j)的倍数,故集合中元素数=n/gcd(i,j)。
#include<iostream> #include<cmath> #include<algorithm> using namespace std; int t,n,a,b,ans,tmp; int gcd(int a,int b) {if (a%b==0) return b; else return gcd(b,a%b);} int main(){ cin>>t; for (int q=1;q<=t;++q){ cin>>n>>a>>b; if (a<b) {tmp=a;a=b;b=tmp;} ans=n/gcd(a,b); cout<<"Case #"<<q<<": "; if (ans%2==0) cout<<"Iaka" ;else cout<<"Yuwgna"; cout<<endl; } return 0; }
HDU 5512 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。