結果

問題 No.2043 Ohuton and Makura
ユーザー ronnyaronnya
提出日時 2022-08-19 21:53:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 337 ms / 2,000 ms
コード長 3,379 bytes
コンパイル時間 2,548 ms
コンパイル使用メモリ 206,660 KB
実行使用メモリ 11,232 KB
最終ジャッジ日時 2024-04-17 00:34:04
合計ジャッジ時間 6,908 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
11,232 KB
testcase_01 AC 12 ms
11,032 KB
testcase_02 AC 197 ms
11,028 KB
testcase_03 AC 186 ms
11,008 KB
testcase_04 AC 294 ms
11,092 KB
testcase_05 AC 210 ms
11,176 KB
testcase_06 AC 46 ms
11,136 KB
testcase_07 AC 320 ms
11,184 KB
testcase_08 AC 62 ms
11,028 KB
testcase_09 AC 206 ms
11,092 KB
testcase_10 AC 277 ms
11,164 KB
testcase_11 AC 212 ms
11,096 KB
testcase_12 AC 12 ms
11,092 KB
testcase_13 AC 277 ms
11,092 KB
testcase_14 AC 13 ms
11,112 KB
testcase_15 AC 13 ms
11,108 KB
testcase_16 AC 12 ms
11,124 KB
testcase_17 AC 334 ms
11,140 KB
testcase_18 AC 284 ms
11,136 KB
testcase_19 AC 333 ms
11,148 KB
testcase_20 AC 337 ms
11,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

using ll   = long long;     using ld   = long double;
using pll  = pair<ll, ll>;  using pld  = pair<ld, ld>;
using vll  = vector<ll>;    using vld  = vector<ld>;
using vpll = vector<pll>;   using vpld = vector<pld>;
using vvll = vector<vll>;   using vvld = vector<vld>;
template<class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> using max_queue = priority_queue<T, vector<T>, less<T>>;

#define rep(i, a, b) for(ll i = (ll)a; i < (ll)b; i++)
#define irep(i, v) for(auto i = (v).begin(); i != (v).end(); i++)
#define SZ(v) (ll)(v).size()
#define ALL(v) (v).begin(), (v).end()
#define SHIFT(a) (1LL << (ll)a)
#define endl '\n'

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-10;
const ld PI  = M_PI;

ll power(ll x, ll y){ ll res = 1; while(y > 0){ if(y & 1){ res *= x; } x *= x; y >>= 1; } return res; }
bool in_grid(ll x, ll y, ll h, ll w){ return (0 <= x && x < h && 0 <= y && y < w); }
template<class T> void pvec(vector<T> &vec){ for(ll i = 0; i < (ll)vec.size(); i++){ if(i){ cout << " "; } cout << vec[i]; } cout << endl; }
template<class T1, class T2> void ppai(pair<T1, T2> &pai){ cout << pai.first << " " << pai.second << endl; }
template<class T> void pvvec(vector<vector<T>> &vec){ for(ll i = 0; i < (ll)vec.size(); i++){ for(ll j = 0; j < (ll)vec[i].size(); j++){ if(j){ cout << " "; } cout << vec[i][j]; } cout << endl; } }
template<class T> void asort(vector<T> &vec){ sort(ALL(vec)); }
template<class T> void rsort(vector<T> &vec){ sort(ALL(vec)); reverse(ALL(vec)); }



class eratosthenes{
  private:
    ll n;
  	vector<ll> min_fact;
  public:
    eratosthenes(ll n): n(n){
      min_fact.resize(n + 1);

      for(ll i = 0; i <= n; i++) min_fact[i] = i;

      for(ll i = 2; i * i <= n; i++){
        if(min_fact[i] == i){
          for(ll j = 2 * i; j <= n; j += i){
            min_fact[j] = i;
          }
        }
      }
    }

    // 素数判定
    bool is_prime(ll x){
      if(x == 0 || x == 1) return false;
      return (min_fact[x] == x);
    }

    // 素因数分解
    vector<pair<ll, ll>> factorize(ll x){
      vector<pair<ll, ll>> res;
      while(x > 1){
        ll p = min_fact[x];
        ll exp = 0;
        while(min_fact[x] == p){
          x /= p;
          exp++;
        }
        res.push_back(make_pair(p, exp));
      }
      return res;
    }

    // 約数列挙
    vector<ll> divisors(ll x){
      vector<ll> res;
      res.push_back(1);
      vector<pair<ll, ll>> tmp = factorize(x);

      ll m = tmp.size();
      for(ll i = 0; i < m; i++){
        ll s = res.size();
        for(ll j = 0; j < s; j++){
          ll v = 1;
          for(ll k = 0; k < tmp[i].second; k++){
            v *= tmp[i].first;
            res.push_back(res[j] * v);
          }
        }
      }
      sort(res.begin(), res.end());
      return res;
    }
};



//using mint = modint<MOD>;

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  cout << fixed << setprecision(20);

  ll a, b, s;
  cin >> a >> b >> s;

  ll ans = 0;
  eratosthenes er(1000000);

  for(ll i = 1; i <= s; i++){
    vll tmp = er.divisors(i);
    for(ll j = 0; j < SZ(tmp); j++){
      ll t = tmp[j], u = i / t;
      if(t <= a && u <= b) ans += (a - t + 1) * (b - u + 1);
    }
  }

  cout << ans << endl;





  return 0;
}
0