結果

問題 No.752 mod数列
ユーザー yukudoyukudo
提出日時 2021-10-31 18:14:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,958 bytes
コンパイル時間 2,034 ms
コンパイル使用メモリ 200,740 KB
実行使用メモリ 18,300 KB
最終ジャッジ日時 2024-10-09 05:55:22
合計ジャッジ時間 13,634 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
18,300 KB
testcase_01 AC 14 ms
11,432 KB
testcase_02 AC 15 ms
11,424 KB
testcase_03 AC 14 ms
11,272 KB
testcase_04 AC 15 ms
11,364 KB
testcase_05 AC 15 ms
11,296 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 804 ms
11,296 KB
testcase_12 AC 1,462 ms
11,372 KB
testcase_13 WA -
testcase_14 AC 1,823 ms
11,376 KB
testcase_15 AC 41 ms
12,020 KB
testcase_16 AC 46 ms
11,968 KB
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[1123456];
const ll M = 1000000;

void init() {
  sqrtP = 1;
  while (sqrtP * sqrtP <= P) sqrtP++;
  sqrtP--;
  pre[0] = 0;
  for (ll i = 1; i <= M; i++) pre[i] = pre[i-1] + (P % i);

}

// a[1] + a[2] + ... + a[N]
ll f(ll N) {
  if (N <= M) {
    return pre[N];
  }
  ll ans = 0;
  if (P < N) {
    ans += P * (N - P);
    N = P;
  }
  ans += pre[sqrtP-1];
  // cout << "prefix ~ " << ans << endl;
  for (ll i = sqrtP+1; 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 << "   ";
    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() {
  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