HDU 5175 Misaki's Kiss again

发表于   |   分类于   |     |   阅读次数

题目描述

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 <= {10}^{10})$

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

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5175

解题思路

题目的意思就是找到满足$GCD(N, M) == N xor M$所有的$M$。令$M = N xor K$，原式：$GCD(N, N xor K) == N xor (N xor K) == K$，由此我们可以发现$K$是$N$的约数，找到所有$N$的约数，判断是不是满足那个等式即可。找约数的话循环只需要循环$\sqrt{N}$次就可以了，这样可以减少计算因数所需要的时间。因为是异或运算，结果可能比约数本身大，如1 xor 2 == 3，还有异或出来结果等于0的舍掉，因为约数中不可能有0，还有就是0的时候多输出一个空行，不然PE。

AC代码

109MS/1596K/G++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

ll a[1000005], factor[1000005];
int make(ll n)
{
    int num = 0;
    ll r = (ll) sqrt(n);
    for (ll i = 1; i <= r; i++)
    {
        if (n % i == 0)
        {
            factor[num] = i;
            num++;
        }
    }
    for (ll i = r; i > 1; i--)
    {
        if (n % i == 0)
        {
            factor[num] = n / i;
            num++;
        }
    }
    return num;
}

int main()
{
    int cse = 1;
    ll n;
    while (~scanf("%I64d", &n))
    {
        int sum = 0, num = make(n);
        for (int i = num - 1; i >= 0; i--)
        {
            if ((n ^ factor[i]) < n && (n ^ factor[i]) > 0 && __gcd(n, n ^ factor[i]) == factor[i])
            {
                a[sum] = n ^ factor[i];
                sum++;
            }
        }
        printf("Case #%d:\n", cse);
        cse++;
        printf("%d\n", sum);
        if (sum > 0)
        {
            printf("%I64d", a[0]);
            for (int i = 1; i < sum; i++)
            {
                printf(" %I64d", a[i]);
            }
        }
        printf("\n");
    }
    return 0;
}