結果

問題 No.752 mod数列
ユーザー yukudoyukudo
提出日時 2021-10-31 17:43:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,996 bytes
コンパイル時間 2,165 ms
コンパイル使用メモリ 194,624 KB
実行使用メモリ 14,016 KB
最終ジャッジ日時 2024-04-17 11:15:56
合計ジャッジ時間 14,057 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,528 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 WA -
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 WA -
testcase_11 AC 764 ms
5,376 KB
testcase_12 AC 1,369 ms
5,376 KB
testcase_13 AC 1,083 ms
5,376 KB
testcase_14 AC 1,734 ms
5,376 KB
testcase_15 AC 28 ms
5,376 KB
testcase_16 WA -
testcase_17 TLE -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

ll P;
ll sqrtP = 1;
ll pre[112345];

void init() {
  sqrtP = (ll)sqrt(P + 0.5);
  pre[0] = 0;
  for (int i = 1; i <= sqrtP; i++) pre[i] = pre[i-1] + (P % i);

}

// a[1] + a[2] + ... + a[N]
ll f(ll N) {
  if (N <= sqrtP) {
    return pre[N];
  }
  ll ans = 0;
  if (P < N) {
    ans += P * (N - P);
    N = P;
  }

  ans += pre[sqrtP];
  for (ll i = sqrtP; i > 0; i--) {
    ll x = P / (i+1);
    ll y = P / (i);
    ll a = P % (x+1);
    ll d = -(P / y);
    // cout << "(" << x << "," << y << "]" << " d=" << d << " a=" << a << endl;
    if (y <= N) {
      ll n = y - x;
      ll w = (2*a+(n-1)*d)*n/2;
      // cout << n << " " << w << endl;
      ans += w;
    } else {
      ll n = N - x;
      ll w = (2*a+(n-1)*d)*n/2;
      // cout << n << " " << w << endl;
      ans += w;
      break;
    }
  }
  // cout << "f(" << N << ")=" << ans << endl;
  return ans;
}

int main2() {
  if (0) {
    P = 23;
    init();
    for (int i = 1; i <= P; i++)
      cout << i << "    " << f(i) << endl;
    return 0;
  }

  P = nextLong();
  ll Q = nextLong();

  init();

  REP(i, Q) {
    ll L = nextLong();
    ll R = nextLong();
    ll ans = f(R) - f(L-1);
    cout << ans << '\n';
  }
  return 0;
}

int main() {
  // int n = 23;
  // for (int k = 1; k <= n; k++) {
  //   cout << k << " : " << (n / k) << " " << (n % k) << endl;
  // }
  // return 0;
#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}
0