結果
問題 | No.152 貯金箱の消失 |
ユーザー |
![]() |
提出日時 | 2015-07-28 08:18:59 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 71 ms / 5,000 ms |
コード長 | 3,638 bytes |
コンパイル時間 | 1,221 ms |
コンパイル使用メモリ | 161,308 KB |
実行使用メモリ | 18,872 KB |
最終ジャッジ日時 | 2024-07-16 04:36:41 |
合計ジャッジ時間 | 2,541 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T> inline T gcd(T a, T b) {return __gcd(a, b);}template<typename T> inline T lcm(T a, T b) {return a / gcd(a, b) * b;}template<typename T> inline T floor(T a, T b) {return a / b * b <= a ? a / b : a / b - 1;}template<typename T> inline T ceil(T a, T b) {return floor(a + b - 1, b);}template<typename T> inline T round(T a, T b) {return floor(a + b / 2);}template<typename T> inline T mod(T a, T b) {return a - floor(a, b) * b;}template<typename T> inline T factorial(T n) {return n <= 1 ? 1 : factorial(n - 1) * n;}namespace arithmetic {template<typename T> class Addition {public:template<typename V> T operator+(const V& v) const {return T(static_cast<const T&>(*this)) += v;}};template<typename T> class Subtraction {public:template<typename V> T operator-(const V& v) const {return T(static_cast<const T&>(*this)) -= v;}};template<typename T> class Multiplication {public:template<typename V> T operator*(const V& v) const {return T(static_cast<const T&>(*this)) *= v;}};template<typename T> class Division {public:template<typename V> T operator/(const V& v) const {return T(static_cast<const T&>(*this)) /= v;}};template<typename T> class Modulus {public:template<typename V> T operator%(const V& v) const {return T(static_cast<const T&>(*this)) %= v;}};}template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic::Multiplication<T> {};template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};class Inverse {private:long long mod;vector<long long> inv;public:Inverse() {}Inverse(long long mod, long long n = 1000000) : mod(mod) {inv = vector<long long>(n, 1);for (int i = 2; i < n; ++i) inv[i] = inv[mod % i] * (mod - mod / i) % mod;}long long operator()(long long a) const {if (a < (int)inv.size()) return inv[a];long long b = mod, x = 1, y = 0;while (b) {long long t = a / b;swap(a -= t * b, b);swap(x -= t * y, y);}return (x %= mod) < 0 ? x + mod : x;}};class Mint : public Arithmetic<Mint> {private:static long long mod;static Inverse inverse;long long val;public:Mint() {}Mint(const long long& val) {this->val = val % mod;if (this->val < 0) this->val += mod;}static void setMod(const long long& m) {mod = m;inverse = Inverse(m);}Mint operator+=(const Mint& m) {val += m.val;if (val >= mod) val -= mod;return *this;}Mint operator-=(const Mint& m) {val -= m.val;if (val < 0) val += mod;return *this;}Mint operator*=(const Mint& m) {val *= m.val;val %= mod;return *this;}Mint operator/=(const Mint& m) {val *= inverse(m.val);val %= mod;return *this;}Mint operator++() {return val += 1;}operator long long() {return val;}Mint identity() const {return 1;}};long long Mint::mod = 1000000007;Inverse Mint::inverse(1000000007);ostream& operator<<(ostream& os, Mint a) {os << (long long)a;return os;}istream& operator>>(istream& is, Mint& a) {long long n;is >> n;a = n;return is;}int main() {int l;cin >> l;Mint::setMod(1000003);Mint res = 0;for (int i = 1; i * i < l; ++i) {for (int j = i % 2 + 1; j < i && 2 * i * (i + j) <= l / 4; j += 2) {if (gcd(i, j) == 1) ++res;}}cout << res << endl;}