Misaki's Kiss again

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1621 Accepted Submission(s): 414

Problem Description

After the Ferries Wheel, many friends hope to receive the Misaki's kiss again,so Misaki numbers them 1,2...N−1,N,if someone's number is M and satisfied the GCD(N,M) equals to N XOR M,he will be kissed again.

Please help Misaki to find all M(1<=M<=N).

Note that:
GCD(a,b) means the greatest common divisor of a and b.
A XOR B means A exclusive or B

Input

There are multiple test cases.

For each testcase, contains a integets N(0<N<=1010)

Output

For each test case,
first line output Case #X:,
second line output k means the number of friends will get a kiss.
third line contains k number mean the friends' number, sort them in ascending and separated by a space between two numbers

Sample Input

3
5
15

Sample Output

Case #1:
1
2
Case #2:
1
4
Case #3:
3
10 12 14

Hint

In the third sample, gcd(15,10)=5 and (15 xor 10)=5, gcd(15,12)=3 and (15 xor 12)=3,gcd(15,14)=1 and (15 xor 14)=1

Source

Valentine's Day Round

题意:找到1=<m<=n里面满足 gcd(n,m) = n xor m 的m的个数.然后输出所有的 m .

题解:数据量 10^10 ，减少到 10^5 就不会超时了.所以我们从异或操作考虑 , n^m = k ---> n^k = m 然后从gcd(n,m)考虑,因为 n<=m 所以 gcd(n,m)必定是 n 的因子,所以我们可以在 O(sqrt(n)) 的时间里面将 n 的因子全部弄出来，然后枚举其因子, n^factor[i] = m ---> gcd(n,m) == factor[i] 那么这个m就是满足条件的,注意一点就是当 m 的个数为 0 的时候，后面要输出空行。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#include <math.h>

using namespace std;

typedef long long LL;

LL factor[];

LL gcd(LL a,LL b){

    return b==?a:gcd(b,a%b);

}

LL ans[];

int main()

{

    LL n;

    int t=;

    while(scanf("%lld",&n)!=EOF){

        factor[] = ;

        int id = ;

        for(LL i=;i*i<=n;i++){

            if(n%i==){

                if(i*i==n){

                    factor[id++] = i;

                }else{

                    factor[id++] = i;

                    factor[id++] = n/i;

                }

            }

        }

        factor[id++] = n;

        int cnt = ;

        for(LL i=;i<id;i++){

            LL M = n^factor[i];

            if(M<||M>n) continue;

            if(gcd(n,M)==factor[i]){

                ans[cnt++] = M;

            }

        }

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

        if(cnt==){

            printf("0\n\n");

        }else{

            sort(ans,ans+cnt);

            printf("%d\n",cnt);

            for(int i=;i<cnt-;i++){

                printf("%lld ",ans[i]);

            }

            printf("%lld\n",ans[cnt-]);

        }

    }

    return ;

}

巴特西

hdu 5175(数论)

Misaki's Kiss again

最新文章

热门文章