Model Solution of GEEK05

geek05.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;

long long ans[MAX];

int main() {
	ios_base::sync_with_stdio(false);
	ans[0] = 1;
	for(int i = 1; i < MAX; ++i) {
		ans[i] = 2 * ans[i-1] % MOD;
	}
	for(int i = 1; i < MAX; ++i) {
		for(int j = 2*i; j < MAX; j += i) {
			ans[j] -= ans[i];
			ans[j] = (ans[j] + MOD) % MOD;
		}
	}
	ans[0] = 0;
	for(int i = 1; i < MAX; ++i) {
		ans[i] = (ans[i] + ans[i-1]) % MOD;
	}
	int t, l, r;
	cin >> t;
	assert(1 <= t && t <= 100000);
	while(t--) {
		cin >> l >> r;
		assert(1 <= l && l <= 100000);
		assert(1 <= r && r <= 100000);
		long long res = (ans[r] - ans[l-1]) % MOD;
		res = (res + MOD) % MOD;
		cout << res << "\n";
	}
	return 0;
}