結果

問題 No.752 mod数列
コンテスト
ユーザー nmnmnmnmnmnmnm
提出日時 2018-09-01 01:35:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 241 ms / 2,000 ms
コード長 2,360 bytes
コンパイル時間 946 ms
コンパイル使用メモリ 103,584 KB
実行使用メモリ 10,568 KB
最終ジャッジ日時 2024-09-14 00:13:02
合計ジャッジ時間 7,787 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef __int128 ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

ostream &operator<<(ostream &os, __int128_t value) {
  if (ostream::sentry(os)) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[64];
    char *d = end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = end(buffer) - d;
    if (os.rdbuf()->sputn(d, len) != len) {
      os.setstate(ios_base::badbit);
    }
  }
  return os;
}

istream &operator>>(istream &is, __int128_t &value) {
  string in;
  is >> in;
  value = 0;
  for (const char &c : in) {
    if ('0' <= c && c <= '9') value = 10 * value + (c - '0');
  }
  if (in[0] == '-') value *= -1;
  return is;
}

ll p;
ll n;

ll d1[100000];
ll d2[100000];
ll d3[100000];
ll d4[100000];
ll d5[100000];

ll f1(ll a, ll d, ll n){
	return a*n+n*(n-1)*d/2;
}

ll f(ll t){
	if(p<=t){
		return d5[n-1]+p*(t-p);
	}
	long long low = 0;
	long long high = n-1;
	
	while(low < high){
	  long long mid = (high + low + 1) >> 1;
	
	  if(d1[mid] <= t){
	    low = mid;
	  }
	  else{
	    high = mid - 1;
	  }
	}
	ll ret = 0;
	if(low>0)ret = d5[low-1];
	ret += f1(d3[low],d2[low],(t-d1[low])+1);
	return ret;
}

int main(void) {
	ll q;
	cin>>p>>q;
	ll i = 0;
	ll index = 1;
	while(1){
		ll a = p/index;
		if(a==0)break;
		ll b = p-a*index;
		ll c = b/a+1;
		d1[i] = index;
		d2[i] = -a;
		d3[i] = b;
		d4[i] = c;
		i++;
		index+=c;
	}
	n = i;
	rep(i,0,n){
		d5[i] += f1(d3[i],d2[i],d4[i]);
	}
	rep(i,1,n){
		d5[i] += d5[i-1];
	}
	rep(i,0,q){
		ll a,b;
		cin>>a>>b;
		cout << f(b)-f(a-1) << endl;
	}
	return 0;
}
0