Valentine's Day Round 1002 Misaki's Kiss again

本文主要是介绍Valentine's Day Round 1002 Misaki's Kiss again，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

Misaki's Kiss again

摩天轮后，一些朋友希望再次得到Misaki的吻，所以Misaki把他们分别编号从1到N，如果他们中有人的编号是M，而且gcd(N,M)=N xor M,那么他以可以得到一个吻。
请帮助Misaki找到所有的M..
Note that:
GCD(a,b) 表示a和b的最大公约数.
AXORB 表示A异或B.

多组测试数据,
对于每组测试数据只有一个数N(0<N<=1010)

第一行Case #x:
第二行一个数count表示有多少个M
第三行有count个数，按升序输出，中间一个空格，表示具体的M..

3
5
15

Case #1:
1
2
Case #2:
1
4
Case #3:
3
10 12 14

第三个样例：gcd(15,10)=5且(15 xor 10)=5, gcd(15,12)=3且(15 xor 12)=3,gcd(15,14)=1且(15 xor 14)=1

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}
int xorr(int a,int b)
{return (a xor b);
}
int a[1000001];
int main()
{long long int n,sum,m;int i,j,ans=0;while(~scanf("%I64d",&n)){sum=0;for(i=1; i<=n; i++){if(gcd(n,i)==xorr(n,i))a[sum++]=i;}sort(a,a+sum);printf("Case #%d:\n%I64d\n", ++ans, sum);for(i=0; i<sum-1; i++){printf("%d ",a[i]);}printf("%d\n",a[sum-1]);}return 0;
}

学习一下别人的优化的代码：

 时间优化63ms

#include <iostream>
#include <algorithm>
using namespace std;long long GCD(long long a,long long b)
{if(b == 0){return a;}else{return GCD(b,a%b);}}int main () {long long n;long long T = 1;while (cin >> n) {long long s[10000];long long k = 0;for (long long i=1; i*i <= n; i++) {if (n % i == 0) {//cout << i <<endl;s[k++] = i;if (i*i != n)s[k++] = n/i;}}long long ans[10000];long long b = 0;for (long long i=0; i<k; i++) {long long m = n ^ s[i];long long g = GCD(n, m);if (g == s[i] && m && m <= n) ans[b++] = m;}sort(ans,ans+b);cout << "Case #" << T++ <<":"<<endl;cout << b << endl;for (long long i=0; i<b; i++) {if (i) cout <<" ";cout << ans[i];}cout << endl;}
}

这篇关于Valentine's Day Round 1002 Misaki's Kiss again的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！