Fox Number (AOJ 2275)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2275

問題

略。

解法

区間篩 or Fox Numberでない数を全列挙。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const int PRIME_SIZE = 2000000;
int psize;
bool bprime[PRIME_SIZE+1];
int prime[PRIME_SIZE+1];
int Eratosthenes(int n) {
  psize = 0;
  memset(bprime, true, sizeof(bprime));
  bprime[0] = bprime[1] = false;
  for (int i = 2; i <= n; i++) {
    if (!bprime[i]) { continue; }
    prime[psize++] = i;
    for (int j = i + i; j <= n; j += i) {
      bprime[j] = false;
    }
  }
  return psize;
}


ll a, b;
ll l, r;
bool ok[1000100];
ll mul(ll lhs, ll rhs) {
  if (lhs * rhs / rhs != lhs) { lhs = 1LL << 60; }
  else { lhs *= rhs; }
  return lhs;
}

int main() {
  Eratosthenes(900000);
  while (scanf("%lld %lld", &a, &b) > 0) {
    MEMSET(ok, true);
    if (a + b <= 1) {
      printf("0\n");
      continue;
    }
    l = max(2LL, a - b);
    r = max(2LL, a + b);
    ll ans = r - l + 1;
    REP(j, psize) {
      ll jprod = mul(prime[j], prime[j]);
      if (jprod > r) { break; }
      REP(i, j) {
        ll prod = mul(prime[i], jprod);
        if (prod > r) { break; }
        while (prod <= r) {
          ll value = (l + prod - 1) / prod * prod;
          while (value <= r) {
            if (ok[value - l] && value / prod % prime[i] != 0) {
              ok[value - l] = false;
              ans--;
            }
            value += prod;
          }
          prod = mul(prod, mul(prime[i], prime[j]));
        }
      }
    }
    printf("%lld\n", ans);
  }
}