結果

問題 No.752 mod数列
ユーザー yukudo
提出日時 2021-10-31 17:43:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,996 bytes
コンパイル時間 2,133 ms
コンパイル使用メモリ 192,316 KB
最終ジャッジ日時 2025-01-25 10:00:28
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 3 TLE * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll nextLong()’:
main.cpp:13:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 | ll nextLong() { ll x; scanf("%lld", &x); return x;}
      |                       ~~~~~^~~~~~~~~~~~

ソースコード

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