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]); } } }