首页 > 代码库 > HDU 5512 题解

HDU 5512 题解

题意:给出n,再给出集合A中的两个整数jkjk,集合满足条件

若j,kAjk,且1<=j-k<=n,则j-k∈A

若j,kAjk,且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 题解