Misaki's Kiss again

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

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<=1010)

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

Sample Output

Case #1:
1
2

Case #2:
1
4

Case #3:
3
10 12 14

思路：gcd（n，m） = norm --->gcd(n,nork) = k;应为m 可以表示为nork的形式，所以，我们只要枚举n的因子k然后判断是否符合即可。

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<string.h>

 5 #include<math.h>

 6 #include<queue>

 7 #include<stdlib.h>

 8 #include<set>

 9 #include<vector>

10 using namespace std;

11 typedef long long LL;

12 LL ans[100000];

13 LL gcd(LL n,LL m);

14 int main(void)

15 {

16     LL N;

17     int cn = 0;

18     while(scanf("%lld",&N)!=EOF)

19     {

20         cn++;

21         ans[0] = -1;

22         printf("Case #%d:\n",cn);

23         if(N == 1)

24         {

25             printf("0\n");

26             printf("\n");

27         }

28         else

29         {

30             int sum = 0;

31             LL i;

32             for(i = 1; i <= sqrt(N); i++)

33             {

34                 if(N%i==0)

35                 {

36                     LL pp = gcd(N,(LL)(N/(LL)i-(LL)1)*(LL)(i));

37                     LL ac = N^((LL)(N/(LL)i-(LL)1)*(LL)(i));

38                     if((N/i-1>=1)&&pp == ac)

39                     {

40                         ans[sum++] = (LL)(N/(LL)i-(LL)1)*(LL)(i);

41                     }

42                     if(N/(LL)i!=i)

43                     {

44                         LL pp = gcd(N,(LL)(i-1)*(LL)(N/i));

45                         LL ac = (LL)(i-1)*(LL)(N/i)^N;

46                                 if(i-1>0&&ac == pp)

47                         {

48                             //printf("1\n");

49                             ans[sum++] = (LL)(i-1)*(LL)(N/i);

50                         }

51                     }

52                 }

53             }

54             printf("%d\n",sum);

55             sort(ans,ans+sum);

56             if(sum>=1)

57                 printf("%lld",ans[0]);

58             for(i = 1; i < sum; i++)

59             {

60                 printf(" %lld",ans[i]);

61             }

62             printf("\n");

63         }

64     }

65     return 0;

66 }

67 LL gcd(LL n,LL m)

68 {

69     if(m == 0)

70         return n;

71     else return gcd(m,n%m);

72 }

巴特西

Misaki's Kiss again（hdu5175）

Misaki's Kiss again

最新文章

热门文章