zoj 3629 Treasure Hunt IV

#include <algorithm>#include <iostream>#include <cstring>#include <iomanip>#include <cstdlib>#include <string>#include <vector>#include <cstdio>#include <cmath>#include <map>using namespace std;bool treasure(int x){ int s = 0; for(int i = 1; i <= x; i++) s += x / i; return s % 2 == 0;}int s[1001];unsigned long long f(long long _x){ if(_x < 0) return 0; if(_x < 100) return s[_x]; unsigned long long x = _x; unsigned long long L = 2, R = 1600000000, M; while(R - L > 1) { M = (L + R) / 2; if(M * (M-1) * 4 <= x) L = M; else R = M; } unsigned long long lefInterval = L * (L-1) * 4; unsigned long long rightInterval = lefInterval + L * 4 - 1; unsigned long long value = lefInterval / 2 + L; if(x <= rightInterval) return value; return value + (x - rightInterval);}int MAIN(){ memset(s, 0, sizeof(s)); s[0] = 1; for(int i = 1; i <= 1000; i++) { s[i] = s[i-1] + treasure(i); } long long L, R; while(cin >> L >> R) cout << f(R) - f(L-1) << endl; return 0;}int main(){ cout << fixed << setprecision(16); ios :: sync_with_stdio(false); return MAIN();}