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

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 <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:
%I64d
", ++ans, sum);
        for(i=0; i<sum-1; i++)
        {
            printf("%d ",a[i]);
        }
        printf("%d
",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;
    }
}