Skip to content

Instantly share code, notes, and snippets.

@likecs
Created November 20, 2017 16:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save likecs/94a5379bafe5e578036d9c559e6acca9 to your computer and use it in GitHub Desktop.
Save likecs/94a5379bafe5e578036d9c559e6acca9 to your computer and use it in GitHub Desktop.
Model Solution 2 of GEEK05
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
long long a[MAX];
int main() {
a[0] = 1;
for(int i = 1; i < MAX; ++i) {
a[i] = (a[i-1] * 2) % MOD;
}
for(int i = 2; i < MAX; ++i) {
int x = sqrt(i);
for(int j = 1; j <= x; ++j) {
if (i % j == 0) {
a[i] = (a[i] - a[j] + MOD) % MOD;
if (j != 1 && j != i/j) {
a[i] = (a[i] - a[i/j] + MOD) % MOD;
}
}
}
}
a[0] = 0;
for(int i = 1; i < MAX; ++i) {
a[i] = (a[i] + a[i-1]) % MOD;
}
int q, l, r;
cin >> q;
while(q--) {
cin >> l >> r;
long long ans = (a[r] - a[l-1] + MOD) % MOD;
cout << ans << "\n";
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment