Valentine's Day Round 1002 Misaki's Kiss again

Valentine's Day Round 1002 Misaki's Kiss again

题意

Misaki's Kiss again

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

问题描述

摩天轮后，一些朋友希望再次得到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

输出描述

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

输入样例

3 5 15

输出样例

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

Hint

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

思路：简单的暴力，但是比赛的时候一直被最后输出的的空格格式卡住，遗憾爆O，以后还是要多多参加！

代码：

#include #include #include #include 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

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

时间优化63ms

#include #include 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 <

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。