結果

問題 No.752 mod数列
ユーザー yukudoyukudo
提出日時 2021-10-31 18:14:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,958 bytes
コンパイル時間 2,377 ms
コンパイル使用メモリ 191,612 KB
最終ジャッジ日時 2025-01-25 10:03:12
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 6 TLE * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
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[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