Description
给你 $n, m$ ,求 $sumlimits_{i=1}^{n}sumlimits_{j=1}^{m} lcm(i,j)$ 。
答案对100000009取模。
多组数据。
Input
第一行有一个正整数 $t$ 表示数据组数
接下来 $t$ 行每行有两个正整数 $n,m$
Output
$t$ 行,第 $i$ 行为第 $i$ 组询问的答案。
Sample input
1
4 5
Sample output
122
HINT
对于100%的数据: $t≤10000,n,m≤10^7$
$100000009$ 不是一个质数。
题解
由 [BZOJ 2154]Crash的数字表格 得到:对于每个询问 $(N,M)$,设 $g(x)=mu(x)cdot x^2$ , $t(x)=sum_{i=1}^{x}i=frac{xcdot(x+1)}{2}$ $$Rightarrow ans=sum_{d=1}^{min{N,M}}dsum_{k=1}^{minleft{leftlfloorfrac{N}{d} ight floor,leftlfloorfrac{M}{d} ight floor ight}}g(k)cdot tleft(leftlfloorfrac{N}{dk} ight floor ight)cdot tleft(leftlfloorfrac{M}{dk} ight floor ight)$$
但这个单个复杂度是 $O(N)$ 的,显然对于 $T$ 组询问 $O(Tcdot N)$ 是不行的。我这么菜是想不出正解的,只能颓题解了。
我们拿出 $dk$ 枚举 egin{aligned}Rightarrow ans&=sum_{dk=1}^{min{N,M}}tleft(leftlfloorfrac{N}{dk}
ight
floor
ight)cdot tleft(leftlfloorfrac{M}{dk}
ight
floor
ight)cdotsum_{d'mid dk}frac{dk}{d'}d'^2mu(d')\&=sum_{dk=1}^{min{N,M}}tleft(leftlfloorfrac{N}{dk}
ight
floor
ight)cdot tleft(leftlfloorfrac{M}{dk}
ight
floor
ight)cdot dksum_{d'mid dk}d'mu(d')end{aligned}
令 $f(x)=xsum_{dmid x}dcdot mu(d)$ $$Rightarrow ans=sum_{dk=1}^{min{N,M}}tleft(leftlfloorfrac{N}{dk}
ight
floor
ight)cdot tleft(leftlfloorfrac{M}{dk}
ight
floor
ight)cdot f(dk)$$
由于 $f(x)$ 是积性函数,线性筛的时候我们枚举数 $i$ 以及质数 $p$ 时,如果:
1. $i$ 是质数, $f(i)=icdot(1-i)$ 。因为 $mu(1)=1,mu(i)=-1$ 。
2. $p
mid i$ , $f(icdot p)=f(i)cdot f(p)$ 。因为 $p$ 为质数,由满足 $p
mid i$ 所以 $i,p$ 互质。满足积性函数的性质。
3. $pmid i$ , $f(icdot p)=f(i)cdot p$ 。因为 $p$ 已经是 $i$ 的一个素因数。所以 $p$ 的出现不会再给求和式子新的贡献,故 $f(icdot p)$ 和 $f(i)$ 中的求和式是相等的,区别就只在前面的系数,分别是 $icdot p$ 和 $i$ ,所以补乘上 $p$ 即可。
1 //It is made by Awson on 2018.1.23 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <cstdio> 9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Abs(a) ((a) < 0 ? (-(a)) : (a)) 17 #define Max(a, b) ((a) > (b) ? (a) : (b)) 18 #define Min(a, b) ((a) < (b) ? (a) : (b)) 19 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b)) 20 #define writeln(x) (write(x), putchar(' ')) 21 #define lowbit(x) ((x)&(-(x))) 22 using namespace std; 23 const int MOD = 100000009; 24 const int N = 1e7; 25 void read(int &x) { 26 char ch; bool flag = 0; 27 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar()); 28 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar()); 29 x *= 1-2*flag; 30 } 31 void write(int x) { 32 if (x > 9) write(x/10); 33 putchar(x%10+48); 34 } 35 36 int n, m, f[N+5]; 37 int isprime[N+5], prime[N+5], tot; 38 39 void get_f() { 40 memset(isprime, 1, sizeof(isprime)); isprime[1] = 0, f[1] = 1; 41 for (int i = 2; i <= N; i++) { 42 if (isprime[i]) prime[++tot] = i, f[i] = (LL)i*(1-i)%MOD; 43 for (int j = 1; j <= tot && i*prime[j] <= N; j++) { 44 isprime[i*prime[j]] = 0; 45 if (i%prime[j]) f[i*prime[j]] = (LL)f[i]*f[prime[j]]%MOD; 46 else {f[i*prime[j]] = (LL)f[i]*prime[j]%MOD; break; } 47 } 48 } 49 for (int i = 2; i <= N; i++) f[i] = (f[i]+f[i-1])%MOD; 50 } 51 int t(int x) {return (LL)(x+1)*x/2%MOD; } 52 int cal(int n, int m) { 53 if (n > m) Swap(n, m); int ans = 0; 54 for (int i = 1, last; i <= n; i = last+1) { 55 last = Min(n/(n/i), m/(m/i)); 56 ans = (ans+(LL)t(n/i)*t(m/i)%MOD*(f[last]-f[i-1])%MOD)%MOD; 57 } 58 return ans; 59 } 60 void work() { 61 read(n), read(m); writeln((cal(n, m)+MOD)%MOD); 62 } 63 int main() { 64 int t; read(t); get_f(); 65 while (t--) work(); 66 return 0; 67 }