首页 > 代码库 > Misaki's Kiss again（hdu5175）

Misaki's Kiss again（hdu5175）

2024-08-26 16:53:51   222人阅读

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
 

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
3
5
15
Sample Output
Case #1:12
Case #2:14
Case #3:310 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         else29         {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）


联系
我们