#67807 (C++11) No.303 割れません

提出ソース

結果

問題	No.303 割れません
ユーザー	anta
提出日時	2015-12-21 23:45:57
言語	C++11 (gcc 11.4.0)
結果	CE (最新) AC (最初)
実行時間	-
コード長	12,068 bytes
コンパイル時間	909 ms
コンパイル使用メモリ	66,472 KB
最終ジャッジ日時	2024-11-14 19:31:38
合計ジャッジ時間	1,530 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ

/usr/bin/ld: /tmp/cc4QPnRp.o: in function `DynamicLibrary::get(char const*) const [clone .isra.0]':
main.cpp:(.text.startup+0xb): undefined reference to `__libc_dlsym'
/usr/bin/ld: /tmp/cc4QPnRp.o: in function `_GLOBAL__sub_I_gmp':
main.cpp:(.text.startup+0x56e): undefined reference to `__libc_dlopen_mode'
collect2: error: ld returned 1 exit status

ソースコード

raw source code

#include <string>
#include <iostream>
#include <cstdlib>
#include <tuple>

#include <gmp.h>

using namespace std;

#if defined(_WIN32)
extern "C" {
	void* __stdcall LoadLibraryA(const char *name);
	void* __stdcall GetProcAddress(void *handle, const char *name);
}
struct DynamicLibrary {
	DynamicLibrary(const char *name) { _handle = LoadLibraryA(name); }
	void *get(const char *name) const { void *p = GetProcAddress(_handle, name); if(!p) cerr << "can't find: " << name << endl, abort(); return p; }
	void *_handle;
} gmp("mpir.dll");
#else
extern "C" {
	void* __libc_dlopen_mode(const char *x, int y);
	void* __libc_dlsym(void *x, const char *y);
}
struct DynamicLibrary {
	DynamicLibrary(const char *name) { _handle = __libc_dlopen_mode(name, 2); }
	void *get(const char *name) const { void *p = __libc_dlsym(_handle, name); if(!p) cerr << "can't find: " << name << endl, abort(); return p; }
	void *_handle;
} gmp("/usr/lib64/libgmp.so.10");
#endif

#define EXPAND_STR_LITERAL_2(a) #a
#define EXPAND_STR_LITERAL(a) EXPAND_STR_LITERAL_2(a)
#define D(name) const auto my_##name = (decltype(::name)*)gmp.get(EXPAND_STR_LITERAL(name))

D(mpz_init); D(mpz_clear);
D(mpz_set); D(mpz_set_ui); D(mpz_set_si); D(mpz_set_d); D(mpz_set_str); D(mpz_swap);
D(mpz_init_set); D(mpz_init_set_ui); D(mpz_init_set_si); D(mpz_init_set_d); D(mpz_init_set_str);
D(mpz_get_ui); D(mpz_get_si); D(mpz_get_d); D(mpz_get_str);
D(mpz_add); D(mpz_add_ui); D(mpz_sub); D(mpz_sub_ui); D(mpz_ui_sub); D(mpz_mul); D(mpz_mul_ui); D(mpz_mul_si); D(mpz_addmul); D(mpz_addmul_ui); D(mpz_submul); D(mpz_submul_ui); D(mpz_mul_2exp); D(mpz_neg); D(mpz_abs);
D(mpz_cdiv_q); D(mpz_cdiv_r); D(mpz_cdiv_qr); D(mpz_cdiv_q_ui); D(mpz_cdiv_r_ui); D(mpz_cdiv_qr_ui); D(mpz_cdiv_ui); D(mpz_cdiv_q_2exp); D(mpz_cdiv_r_2exp); D(mpz_fdiv_q); D(mpz_fdiv_r); D(mpz_fdiv_qr); D(mpz_fdiv_q_ui); D(mpz_fdiv_r_ui); D(mpz_fdiv_qr_ui); D(mpz_fdiv_ui); D(mpz_fdiv_q_2exp); D(mpz_fdiv_r_2exp); D(mpz_tdiv_q); D(mpz_tdiv_r); D(mpz_tdiv_qr); D(mpz_tdiv_q_ui); D(mpz_tdiv_r_ui); D(mpz_tdiv_qr_ui); D(mpz_tdiv_ui); D(mpz_tdiv_q_2exp); D(mpz_tdiv_r_2exp); D(mpz_divexact); D(mpz_divexact_ui); D(mpz_divisible_p); D(mpz_divisible_ui_p); D(mpz_divisible_2exp_p); D(mpz_congruent_p); D(mpz_congruent_ui_p); D(mpz_congruent_2exp_p);
D(mpz_powm); D(mpz_powm_ui); D(mpz_pow_ui); D(mpz_ui_pow_ui);
D(mpz_root); D(mpz_rootrem); D(mpz_sqrt); D(mpz_sqrtrem); D(mpz_perfect_power_p); D(mpz_perfect_square_p);
D(mpz_probab_prime_p); D(mpz_nextprime); D(mpz_gcd); D(mpz_gcd_ui); D(mpz_gcdext); D(mpz_lcm); D(mpz_lcm_ui); D(mpz_invert); D(mpz_jacobi); D(mpz_legendre); D(mpz_kronecker); D(mpz_kronecker_si); D(mpz_kronecker_ui); D(mpz_si_kronecker); D(mpz_ui_kronecker); D(mpz_remove); D(mpz_fac_ui); D(mpz_bin_ui); D(mpz_bin_uiui); D(mpz_fib_ui); D(mpz_fib2_ui); D(mpz_lucnum_ui); D(mpz_lucnum2_ui);
D(mpz_cmp); D(mpz_cmp_d); D(_mpz_cmp_si); D(_mpz_cmp_ui);
D(mpz_and); D(mpz_ior); D(mpz_xor); D(mpz_com); D(mpz_popcount); D(mpz_hamdist); D(mpz_scan0); D(mpz_scan1); D(mpz_setbit); D(mpz_clrbit); D(mpz_combit); D(mpz_tstbit);
D(mpz_urandomb); D(mpz_urandomm); D(mpz_rrandomb);
D(mpz_import); D(mpz_export);
D(mpz_fits_ulong_p); D(mpz_fits_slong_p); D(mpz_fits_uint_p); D(mpz_fits_sint_p); D(mpz_fits_ushort_p); D(mpz_fits_sshort_p); D(mpz_sizeinbase);
D(_mpz_realloc); D(mpz_getlimbn); D(mpz_size);

#undef D

class BigInt {
	mpz_t _z;
public:
	BigInt() { my_mpz_init(_z); }
	BigInt(const BigInt &x) { my_mpz_init_set(_z, x._z); }
	BigInt(BigInt &&x) { my_mpz_init(_z); swap(x); }
	BigInt(mpz_t x) { my_mpz_init_set(_z, x); }
	BigInt &operator=(const BigInt &x) { my_mpz_set(_z, x._z); return *this; }
	BigInt &operator=(BigInt &&x) { swap(x); return *this; }
	BigInt &operator=(mpz_t x) { my_mpz_set(_z, x); return *this; }
	~BigInt() { my_mpz_clear(_z); }
	void swap(BigInt &x) { my_mpz_swap(_z, x._z); }
	void swap(mpz_t x) { my_mpz_swap(_z, x); }

	BigInt(mp_limb_t x) { my_mpz_init_set_ui(_z, x); }
	BigInt(mp_limb_signed_t x) { my_mpz_init_set_si(_z, x); }
	BigInt(unsigned x) { my_mpz_init_set_ui(_z, x); }
	BigInt(int x) { my_mpz_init_set_si(_z, x); }
	BigInt(double x) { my_mpz_init_set_d(_z, x); }
	BigInt(const char *x, int base = 10) { my_mpz_init_set_str(_z, x, base); }

	BigInt &operator=(mp_limb_t x) { my_mpz_set_ui(_z, x); return *this; }
	BigInt &operator=(mp_limb_signed_t x) { my_mpz_set_si(_z, x); return *this; }
	BigInt &operator=(unsigned x) { return *this = (mp_limb_t)x; }
	BigInt &operator=(int x) { return *this = (mp_limb_signed_t)x; }
	BigInt &operator=(double x) { my_mpz_set_d(_z, x); return *this; }
	BigInt &operator=(const char *x) { my_mpz_set_str(_z, x, 10); return *this; }

	explicit operator mp_limb_t() const { return my_mpz_get_ui(_z); }
	explicit operator mp_limb_signed_t() const { return my_mpz_get_si(_z); }
	explicit operator unsigned() const { return (unsigned)my_mpz_get_ui(_z); }
	explicit operator int() const { return (int)my_mpz_get_si(_z); }
	explicit operator double() const { return my_mpz_get_d(_z); }

	char *get_str(char *p = nullptr, int base = 10) const {
		if(!p) p = new char[my_mpz_sizeinbase(_z, base) + 2];
		return my_mpz_get_str(p, base, _z);
	}
	std::string to_string(int base = 10) const {
		char *p = get_str(nullptr, base);
		std::string res(p);
		delete[] p;
		return res;
	}

	BigInt &operator+=(const BigInt &x) { my_mpz_add(_z, _z, x._z); return *this; }
	BigInt &operator+=(mp_limb_t x) { my_mpz_add_ui(_z, _z, x); return *this; }
	BigInt operator+(const BigInt &x) const { BigInt r; my_mpz_add(r._z, _z, x._z); return r; }
	BigInt operator+(mp_limb_t x) const { BigInt r; my_mpz_add_ui(r._z, _z, x); return r; }
	friend BigInt operator+(mp_limb_t x, const BigInt &y) { BigInt r; my_mpz_add_ui(r._z, y._z, x); return r; }
	BigInt &operator-=(const BigInt &x) { my_mpz_sub(_z, _z, x._z); return *this; }
	BigInt &operator-=(mp_limb_t x) { my_mpz_sub_ui(_z, _z, x); return *this; }
	BigInt operator-(const BigInt &x) const { BigInt r; my_mpz_sub(r._z, _z, x._z); return r; }
	BigInt operator-(mp_limb_t x) const { BigInt r; my_mpz_sub_ui(r._z, _z, x); return r; }
	friend BigInt operator-(mp_limb_t x, const BigInt &y) { BigInt r; my_mpz_ui_sub(r._z, x, y._z); return r; }

	BigInt &operator*=(const BigInt &x) { my_mpz_mul(_z, _z, x._z); return *this; }
	BigInt &operator*=(mp_limb_t x) { my_mpz_mul_ui(_z, _z, x); return *this; }
	BigInt operator*(const BigInt &x) const { BigInt r; my_mpz_mul(r._z, _z, x._z); return r; }
	BigInt operator*(mp_limb_t x) const { BigInt r; my_mpz_mul_ui(r._z, _z, x); return r; }
	friend BigInt operator*(mp_limb_t x, const BigInt &y) { BigInt r; my_mpz_mul_ui(r._z, y._z, x); return r; }

	BigInt &operator<<=(size_t x) { my_mpz_mul_2exp(_z, _z, x); return *this; }
	BigInt operator<<(size_t x) const { BigInt r; my_mpz_mul_2exp(r._z, _z, x); return r; }

	BigInt operator-() const { BigInt r; my_mpz_neg(r._z, _z); return r; }
	friend BigInt abs(const BigInt &x) { BigInt r; my_mpz_abs(r._z, x._z); return r; }

	BigInt &operator/=(const BigInt &x) { my_mpz_tdiv_q(_z, _z, x._z); return *this; }
	BigInt &operator/=(mp_limb_t x) { my_mpz_tdiv_q_ui(_z, _z, x); return *this; }
	BigInt operator/(const BigInt &x) const { BigInt r; my_mpz_tdiv_q(r._z, _z, x._z); return r; }
	BigInt operator/(mp_limb_t x) const { BigInt r; my_mpz_tdiv_q_ui(r._z, _z, x); return r; }
	BigInt &operator%=(const BigInt &x) { my_mpz_tdiv_r(_z, _z, x._z); return *this; }
	BigInt &operator%=(mp_limb_t x) { my_mpz_tdiv_r_ui(_z, _z, x); return *this; }
	BigInt operator%(const BigInt &x) const { BigInt r; my_mpz_tdiv_r(r._z, _z, x._z); return r; }
	BigInt operator%(mp_limb_t x) const { BigInt r; my_mpz_tdiv_r_ui(r._z, _z, x); return r; }

	std::pair<BigInt, BigInt> quotRem(const BigInt &x) { BigInt q, r; my_mpz_tdiv_qr(q._z, r._z, _z, x._z); return make_pair(q, r); }
	std::pair<BigInt, BigInt> quotRem(mp_limb_t x) { BigInt q, r; my_mpz_tdiv_qr_ui(q._z, r._z, _z, x); return make_pair(q, r); }

	BigInt mod(const BigInt &x) const { BigInt r; my_mpz_fdiv_r(r._z, _z, x._z); return r; }
	mp_limb_t mod(mp_limb_t x) const { return my_mpz_fdiv_ui(_z, x); }

	BigInt &operator>>=(size_t x) { my_mpz_tdiv_q_2exp(_z, _z, x); return *this; }
	BigInt operator>>(size_t x) const { BigInt r; my_mpz_tdiv_q_2exp(r._z, _z, x); return r; }

	BigInt divexact(const BigInt &x) const { BigInt r; my_mpz_divexact(r._z, _z, x._z); return r; }
	BigInt divexact(mp_limb_t x) const { BigInt r; my_mpz_divexact_ui(r._z, _z, x); return r; }

	BigInt powmod(const BigInt &x, const BigInt &mod) const { BigInt r; my_mpz_powm(r._z, _z, x._z, mod._z); return r; }
	BigInt powmod(mp_limb_t x, const BigInt &mod) const { BigInt r; my_mpz_powm_ui(r._z, _z, x, mod._z); return r; }

	BigInt pow(mp_limb_t x) const { BigInt r; my_mpz_pow_ui(r._z, _z, x); return r; }

	bool is_prime(int reps = 15) const { return my_mpz_probab_prime_p(_z, reps) != 0; }
	BigInt next_prime() const { BigInt r; my_mpz_nextprime(r._z, _z); return r; }

	friend BigInt gcd(const BigInt &x, const BigInt &y) { BigInt r; my_mpz_gcd(r._z, x._z, y._z); return r; }
	friend BigInt gcd(const BigInt &x, mp_limb_t y) { BigInt r; my_mpz_gcd_ui(r._z, x._z, y); return r; }
	friend void gcd_ext(const BigInt &a, const BigInt &b, BigInt &g, BigInt &s, BigInt &t) { my_mpz_gcdext(g._z, s._z, t._z, a._z, b._z); }
	friend BigInt lcm(const BigInt &x, const BigInt &y) { BigInt r; my_mpz_lcm(r._z, x._z, y._z); return r; }
	friend BigInt lcm(const BigInt &x, mp_limb_t y) { BigInt r; my_mpz_lcm_ui(r._z, x._z, y); return r; }

	BigInt invert(const BigInt &mod) const { BigInt r; my_mpz_invert(r._z, _z, mod._z); return r; }

	static BigInt factorial(mp_limb_t x) { BigInt r; my_mpz_fac_ui(r._z, x); return r; }
	static BigInt binomial(const BigInt &x, mp_limb_t y) { BigInt r; my_mpz_bin_ui(r._z, x._z, y); return r; }
	static BigInt binomial(mp_limb_t x, mp_limb_t y) { BigInt r; my_mpz_bin_uiui(r._z, x, y); return r; }

	static BigInt fib(mp_limb_t x) { BigInt r; my_mpz_fib_ui(r._z, x); return r; }
	static std::pair<BigInt, BigInt> fib2(mp_limb_t x) { BigInt a, b; my_mpz_fib2_ui(a._z, b._z, x); return std::make_pair(a, b); }

	int compare_to(const BigInt &x) const { return my_mpz_cmp(_z, x._z); }
	int compare_to(double x) const { return my_mpz_cmp_d(_z, x); }
	int compare_to(mp_limb_signed_t x) const { return my__mpz_cmp_si(_z, x); }
	int compare_to(mp_limb_t x) const { return my__mpz_cmp_ui(_z, x); }
	int compare_to(int x) const { return my__mpz_cmp_si(_z, x); }
	int compare_to(unsigned x) const { return my__mpz_cmp_ui(_z, x); }

	bool operator< (const BigInt &x) const { return compare_to(x) <  0; }
	bool operator<=(const BigInt &x) const { return compare_to(x) <= 0; }
	bool operator==(const BigInt &x) const { return compare_to(x) == 0; }
	bool operator>=(const BigInt &x) const { return compare_to(x) >= 0; }
	bool operator> (const BigInt &x) const { return compare_to(x) >  0; }

	BigInt &operator&=(const BigInt &x) { my_mpz_and(_z, _z, x._z); return *this; }
	BigInt operator&(const BigInt &x) const { BigInt r; my_mpz_and(r._z, _z, x._z); return r; }
	BigInt &operator|=(const BigInt &x) { my_mpz_ior(_z, _z, x._z); return *this; }
	BigInt operator|(const BigInt &x) const { BigInt r; my_mpz_ior(r._z, _z, x._z); return r; }
	BigInt &operator^=(const BigInt &x) { my_mpz_xor(_z, _z, x._z); return *this; }
	BigInt operator^(const BigInt &x) const { BigInt r; my_mpz_xor(r._z, _z, x._z); return r; }
	BigInt operator~() const { BigInt r; my_mpz_com(r._z, _z); return r; }

	friend std::istream &operator>>(std::istream &i, BigInt &x) {
		std::string str;
		i >> str;
		x = BigInt(str.c_str());
		return i;
	}

	friend std::ostream &operator<<(std::ostream &o, const BigInt &x) {
		return o << x.to_string();
	}
};

int main() {
	BigInt x;
	x += 1;
	x *= 2;

	int n;
	while(~scanf("%d", &n)) {
		if(n == 2) {
			puts("3\nINF");
		} else {
			BigInt ans;
			if(n % 2 == 1) {
				ans = BigInt::fib(n);
			} else {
				BigInt a, b;
				std::tie(a, b) = BigInt::fib2(n / 2);
				ans = (a * b) << 1;
			}

			printf("%d\n", n);
			string s = ans.to_string();
			puts(s.c_str());
		}
	}
	return 0;
}

yukicoder

結果

コンパイルメッセージ

ソースコード