- 1#include 2#include 3#include 4#include 5#include 6#include 7 using namespace std;
- 8 typedef long long ll;
- 9 const int maxn = 1e7 + 1;
- 10 const int mod = 1e8 + 9;
- 11 int cnt;
- 12 int h[maxn];
- 13 int pri[maxn];
- 14 int sum[maxn];
- 15 bool vis[maxn];
- 16 inline void Scan(int & x) 17 {
- 18 char c;
- 19 bool o = false;
- 20
- while (!isdigit(c = getchar())) o = (c != ' - ') ? o: true;
- 21 x = c - '0';
- 22
- while (isdigit(c = getchar())) x = x * 10 + c - '0';
- 23
- if (o) x = -x;
- 24
- }
- 25 inline void Sieve() 26 {
- 27 h[1] = 1;
- 28
- for (int i = 2; i <= maxn; ++i) 29 {
- 30
- if (!vis[i]) pri[++cnt] = i,
- h[i] = (( - (long long) i * i % mod) + mod + i) % mod;
- 31
- for (int j = 1; j <= cnt; ++j) 32 {
- 33 int s = pri[j];
- 34 long long k = (long long) i * s;
- 35
- if (k > maxn) break;
- 36 vis[k] = true;
- 37
- if (! (i % s)) 38 {
- 39 h[k] = (long long) s * h[i] % mod;
- 40
- break;
- 41
- }
- 42
- else h[k] = (long long) h[s] * h[i] % mod;
- 43
- }
- 44
- }
- 45
- for (int i = 1; i <= maxn; ++i) sum[i] = (sum[i - 1] + h[i]) % mod;
- 46
- }
- 47 inline int Sum(int n, int m) 48 {
- 49
- return ((long long) n * (n + 1) >> 1) % mod * (((long long) m * (m + 1) >> 1) % mod) % mod;
- 50
- }
- 51 inline int Mobius(int n, int m) 52 {
- 53 int res = 0,
- last = 0;
- 54
- if (n > m) swap(n, m);
- 55
- for (int i = 1; i <= n; i = last + 1) 56 {
- 57 last = min(n / (n / i), m / (m / i));
- 58 res = (res + (long long) Sum(n / i, m / i) * ((sum[last] - sum[i - 1] + mod) % mod) % mod) % mod;
- 59
- }
- 60
- return res;
- 61
- }
- 62 int main() 63 {
- 64 Sieve();
- 65 int n;
- 66 Scan(n);
- 67 int a,
- b;
- 68
- while (n--) 69 {
- 70 Scan(a),
- Scan(b);
- 71 printf("%d\n", Mobius(a, b));
- 72
- }
- 73
- }
来源: http://www.bubuko.com/infodetail-2035680.html