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); } }