TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

12 /
04
2021
 

Fraction Floor Sum

問題

E – Fraction Floor Sum
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

解法 1

  1. \(i <= N\) まで繰り返す。
  2. \(N/i = x\) を求める。
  3. \(x\) が変わらない最大の \(i(=maxI)\) を求める。
  4. 3.より \(x\) が変わるのは \(maxI+1(=nextI)\) になったとき。
  5. 答えに \((nextI-i) * x\) を加える。
  6. \(i = nextI\) に更新する。

コード例 1

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int main() {
  ll N;
  cin >> N;

  ll ans = 0;
  ll i = 1;
  while(i <= N) {
    ll x = N / i;

    // x が変わらない最大の i
    ll maxI = N / x;

    // x が変わった時の i
    ll nextI = maxI + 1;

    ans += (nextI - i) * x;

    i = nextI;
  }

  cout << ans << endl;
  return 0;
}

解法 2

  1. \(i * i \leq N\) を満たす最大の \(i\) を探す。
  2. \(y = N / x\) にして、 \(1 <= x <= i\) のときの \(y\)(整数の個数)の総和を計算する(下図の青の部分)。
  3. \(x = N / y\) にして、 \(1 <= y <= i\) のときの \(x\)(整数の個数)の総和を計算する(下図の赤の部分)。
    ( 2. と 3. でやることは同じ)
  4. 2. と 3. から重なっている部分(下図の青と赤が重なっている部分)の整数の個数を数える。
  5. 2. + 3. – 4. が答え。

コード例 2

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int main() {
  ll N;
  cin >> N;

  // 1.
  ll i = 1;
  while(i * i < N) {
    i += 1;
  }

  // 2.と3.
  ll v = 0;
  for(int j = 1; j <= i; ++j) {
    v += N / j;
  }

  // 4.重なっている部分
  ll v2 = 0;
  for(int j = 1; j <= i; ++j) {
    v2 += min(i, N / j);
  }

  // 5.
  cout << v + v - v2 << endl;
  return 0;
}