yukicoder No.51 やる気の問題 解説

問題文

解説

愚直に一日ごとに確かめていくのがいいだろう。
具体的には次のようにする。
まず、これは$i$日目（$i\leqq D-1$）の計算を説明する。
・$floor(W/(D-i+1)^2)$を$W$から引く。
これだけ。
そして、求めたい最終日の作業量についてだが、$floor(W/1)$=$W$なので、$D-1$日目までの作業の残りが答えになる。
よってどんどん$W$を引いていって残った$W$が答えになる。
実行時間は$O(D)$。
$D*D\geqq 2^{31}$なので、long long型を使おう。

C++での解答例

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
  ll w,d;cin>>w>>d;
  for(ll i=1;i<d;i++)
    //引き算
    w-=floor(w/((d-i+1)*(d-i+1)));
  cout<<w<<endl;
}