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
/*************************************************************************
> File Name: bc30-b.cpp
> Author: ALex
> Mail: zchao1995@gmail.com
> Created Time: 2015年02月14日 星期六 19时32分44秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
vector <LL> yueshu, ans;
LL gcd (LL A, LL B)
{
return B ? gcd (B, A % B) : A;
}
int main ()
{
LL n;
int icase = 1;
while (~scanf("%I64d", &n))
{
yueshu.clear();
int tmp = sqrt(n + 0.5);
for (int i = 1; i <= tmp; ++i)
{
if (n % i == 0)
{
yueshu.push_back (i);
if (i != n / i)
{
yueshu.push_back (n / i);
}
}
}
ans.clear();
int size = yueshu.size();
for (int i = 0; i < size; ++i)
{
LL u = yueshu[i];
if ((u ^ n) <= n && (u ^ n) != 0 && gcd (n, u ^ n) == u)
{
ans.push_back (u ^ n);
}
}
printf("Case #%d:\n", icase++);
size = ans.size();
sort (ans.begin(), ans.end());
printf("%d\n", size);
if (size != 0)
{
printf("%I64d", ans[0]);
for (int i = 1; i < size; ++i)
{
if (ans[i] == ans[i - 1])
{
continue;
}
printf(" %I64d", ans[i]);
}
}
printf("\n");
}
return 0;
}