Misaki's Kiss again

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 201 Accepted Submission(s): 57

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
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

HintIn 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

題目連接：http://acm.hdu.edu.cn/showproblem.php?pid=5175

題目大意：找到滿足gcd(N,M)==NxorM的M值(1<=M<=N)

題目分析：令M = N xor K，原式：gcd(N，N xor K) == N xor (N xor K) == K，由此我們可以發現K是N的約數，找到所有N的約數，判斷是不是滿足那個等式即可，因為是異或運算，結果可能比約數本身大，如1xor2==3，還有異或出來結果等於0的捨掉(它本身)gcd(n,n) != nxorn，還有就是0的時候多輸出一個空行，不然pe

#include 
#include 
#define ll long long
int const MAX = 1e5;
ll fac[MAX], ans[MAX];

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;  
}

int main()
{
    int ca = 1;
    ll n;
    while(scanf("%I64d", &n) != EOF)
    {
        int cnt1 = 0, cnt2 = 0;
        ll tmp = sqrt(n);
        for(ll i = 1; i <= tmp; i++)
            if(n % i == 0)
                fac[cnt1++] = i;
        for(ll i = tmp; i >= 1; i--)
            if(n % i == 0 && i != 1)
                fac[cnt1++] = n / i;
        for(int i = cnt1 - 1; i >= 0; i--)
            if(fac[i] == gcd(n, n^fac[i]) && (n^fac[i]) != 0 && (n^fac[i]) <= n)
                ans[cnt2++] = (n^fac[i]);
        printf("Case #%d:\n%d\n", ca++, cnt2);
        if(cnt2 == 0)
            printf("\n");
        for(int i = 0; i < cnt2; i++)
        {
            if(i != cnt2 - 1)
                printf("%I64d ", ans[i]);
            else
                printf("%I64d\n", ans[i]);
        }
    }   
}