ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

Valentine's Day Round (BestCoder #030) B : Misaki's Kiss again

概要

自然数Nが与えられる。

gcd(N, M) == (N xor M)を満たす自然数Mを全て列挙せよ。

0<N<=10^10
1<=M<=N

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=568

解法

Nがとても大きいので全通り試すことはできない。

B = gcd(N, M)とするとBにはNの約数しか入らないので、Nの約数を全て列挙し、それら値に対して上記の等式が成り立つか試せば良い。

Bが分かれば、M = N xor BとなりMが分かる。
そしてgcd(N, M)がBと一致するか確かめれば良いことになる。

Nの約数は、sqrt(N)まで調べれば全て列挙することができる。
(Nがiで割り切れるならiとN/iは約数)

O(sqrt(N))なので、Nがとても大きくても間に合う。

ソースコード

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
#include <cstring>

using namespace std;

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back

typedef long long int lli;

lli gcd(lli a, lli b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

// gcd(N, a) == N ^ a == b
// 1 <= a <= N
bool check(lli N, lli b) {
  lli a = N ^ b;

  if(a < 1 || N < a) return false;
  if(gcd(N, a) != b) return false;
  return true;
}

int main() {
  int T = 1;
  lli N;

  while(cin >> N) {
    vector<lli> ans;

    for(lli b = 1; b * b <= N; b++) {
      if(N % b) continue;

      if(check(N, b)) ans.push_back(N ^ b);
      if(N / b != b && check(N, N / b)) ans.push_back(N ^ (N / b));
    }

    sort(all(ans));

    cout << "Case #" << T++ << ":" << endl;
    cout << ans.size() << endl;
    rep(i, ans.size()) {
      if(i) cout << " ";
      cout << ans[i];
    }
    cout << endl;
  }
  
  return 0;
}