hdu 5175 Misaki's Kiss again（GCD和异或）

题意：

给一个数N。

如果GCD(N,M) = N XOR M，则称M是一个kiss 　　　　 1<=M<=N

问总共有多少个kiss。并且列出所有的值。

思路：

思路一：枚举M。有大量的GCD(N,M)值相等。但是N XOR M=X。当X是定值是，M一定只有一个。所以这个方法明显有大量重复。

　　　　发现知道GCD(N,M)的值，可直接求出M。搞定。

令gcd(n,m)=d，可知道d是n的约数

有d=(n xor m)=(m xor n)，所以m=(d xor n)。

可发现gcd(n,(d xor n))=d。

*注意：gcd(a,b) 当a或b为零时，gcd(a,b)的值为1。这个要单独判断。

　　还有一个(d xor n)有可能大于n。这个也要单独判断。

代码：

ll N;

ll gcd(ll a,ll b){

    if(b==0) return a;

    return gcd(b,a%b);

}

int T = 0;

ll ans[100005];

int kissNum;

int main(){

    while(scanf("%I64d",&N)!=EOF){

        kissNum = 0;

        for(ll i=1;i*i<=N;++i){

            if(N%i==0){

                ll x = N^i;

                if(x>0 && x<=N && gcd(N,x)==i){

                    ans[++kissNum] = x;

                }

                ll t = N/i;

                if(t!=i){

                    ll xx = N^t;

                    if(xx>0 && xx<=N && gcd(N,xx)==t){

                        ans[++kissNum] = xx;

                    }

                }

            }

        }

        printf("Case #%d:\n%d\n",++T,kissNum);

        if(kissNum>0){

            sort(ans+1,ans+1+kissNum);

            printf("%I64d",ans[1]);

            rep(i,2,kissNum) printf(" %I64d",ans[i]);

        }

        cout<<endl;

    }

    return 0;

}

巴特西

hdu 5175 Misaki's Kiss again（GCD和异或）

最新文章

热门文章