D - Remainder Reminder 〜ABC090〜

問題

D - Remainder Reminder

感想

かなり手こずった．．． 簡単な方のD問題のはずなのだが．

考え

a, b, k のいずれか一つを全探索する方法でない限り，制約条件的に時間以内にACすることはできない．

bに注目することで，余りの周期性を利用することができるためbとaの上限nからあまりがk以上の組み合わせを求めることができる．

aやらkを全探索することを考えてずっと手こずっていました．．．．．悔しい．

Accepted Program

#include <iostream>
#include <math.h>

using namespace std;
#define ll long long

int main () {
  ll n, k;
  ll ans = 0;
  cin >> n >> k;
  if (k == 0) {
    cout << n * n << endl;
    return 0;
  }
  for (ll i = k + 1; i <= n; i++) {
    ans += i - k;
    ll sub = n % i;
    if (sub >= k) {
      ans += sub - k + 1;  
    }
    sub = n / i - 1;
    ans += sub * (i - k);
  }
  cout << ans << endl;
}