F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Misaki's Kiss again

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


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

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-09-27 22:29:20, Gzip enabled